Is this variant of the subset sum problem easy/known?
Given an integer $m$, and a set of positive integers $A = \{x_1, x_2, ..., x_n\}$ such that every $x_i$ has at most $k=2$ bits set to $1$ ($x_i = 2^{b_{i_1}}+2^{b_{i_2}},\;\; b_{i_1},b_{i_2}\geq 0$); is there a subset $A' \subseteq A$ such that the sum of its elements is equal to $m$ ?
Is it in $\sf{P}$? Is it still $\sf{NP}$-complete?
And if every $x_i$ has at most $k=3$ bits set to $1$? For $k=1$ the problem is trivial.
It is still $\sf{NP}$-complete, even for $k=2$. Given an instance of subset sum, we can transform it in to this variant by splitting up the numbers and adding some extra bits.
First, the sum of all numbers in the problem will be less than $2^m$ for some value of $m$.
Now, let's take a number $n$ from the original problem which has $k$ bits set. We will split this number in to $k$ numbers with exactly 2 bits set such that the sum of those numbers is $n+2^{k+m}$. We can do this recursively, by finding $\lceil{k}\rceil$ numbers that sum up to the first $\lceil{k}\rceil$ bits plus $2^{k+m-1}$ and $\lfloor{k}\rfloor$ numbers that sum up to the last $\lfloor{k}\rfloor$ bits plus $2^{k+m-1}$.
In addition to that number we will also add the number $2^{k+m}$ to the problem. A solution must either contain this number or all of the $k$ numbers constructed previously. If the original target value was $t$ the new target value will be $t+2^{k+m}$.
If the original problem had more than one number, we can repeat this process taking $k+m+1$ for the new value of $m$.
There are only two ways the bit at position $k+m$ can be set: the answer can contain the number $2^{k+m}$ or all of the $k$ numbers that sum up to $n+2^{k+m}$. So we have reduced subset sum to your subset sum variant.
As an example, let's take ${\{2,3,5\}}$ with target value $7$. This problem could be encoded as the subset sum variant presented here by taking the following binary numbers:
2 gets mapped to $0100\ 1$ and $0000\ 1$. (Using the extra bit is not strictly necessary here.)
3 gets mapped to $1000\ 00\ 1, 0100\ 00\ 1$ and $0000\ 00\ 01$
5 gets mapped to $1000\ 00\ 000\ 1, 0010\ 00\ 000\ 1$ and $0000\ 00\ 000\ 01$.
The new target value would become $1110\ 10\ 010\ 01$.
If the original problem is represented with $n$ bits, then the transformed problem has at most $O(n^4)$ bits. The original problem will have at most $O(n)$ numbers each with at most $O(n)$ bits, so the sum of all of them is also O(n). The transformed problem will have $O(n^2)$ numbers (since each $n$-bit number is split in to $n+1$ $2$-bit numbers, with their length being at most $O(n^2)$ since we use $n$ additional bits for each number. So the total size of the transformed problem is $O(n^4)$ bits.
This is information extracted from question by Vor.
For $k \geq 3$ the problem remains NP-complete. I found a quick reduction from monotone X-SAT (see the schema of the reduction here).
The problem remains NP-complete even if $k = 2$, see Tom's answer for details. Here is a small representation of his reduction from SUBSET SUM:
