Smallest integer with k 1-bits that is the sum of two integers with g,h 1-bits respectively

Question

Given integers $g, h, k, n$ how to find the smallest integer with $k\ 1$-bits that is the sum of two integers with $g, h\ 1$-bits respectively. Moreover, all three numbers (summands and sum) can have at most $n$ bits, i.e. the result is the n-bit number with $k\ 1$'s and $(k - n)$ zeros, for instance $\underbrace{0...0}_\text{n -k}\underbrace{1...1}_\text{k}$. These $1$-bits don't have to be consecutive. Of course, such a number may not exist at all. You can think of this output integer (if it exists) as a permutation of a set of $n - k$ zeroes and $k$ ones.

I have a strong feeling that this is a dynamic programming problem but I can't get what is a subproblem here. I actually have no clue about DP relation for this problem. Could anyone give me some hints?

UPDATE. I've came up with the following plan:

Let $dp(g, h, k, n, carry)$ be such a sum, where $carry$ is an optional bit for carrying. Then $dp(g, h, k, n + 1, 0)$ = $min\{dp(g,h,k, n,0),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(0, 0) \\2^n + dp(g,h,k - 1, n,1)\\ 2^n + dp(g - 1, h, k-1, n, 0), \ \ :(1, 0) \\ 2^n + dp(g, h - 1, k - 1, n, 0), \ \ :(0, 1) \}$

$dp(g, h, k, n + 1, 1)$ = $min\{dp(g - 1, h, k, n, 1),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(1, 0) \\ dp(g, h - 1, k , n, 1),\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ :(0, 1) \\ dp(g-1,h-1,k, n,0)\ \ \ \ \ \ \ \ \ \ \ \ \ \ :(1, 1)\\ 2^n + dp(g - 1, h - 1, k - 1, n, 1)\}$

I realized that this is too complex for me to handle on my own. I don't know what are the initial values (or base case of recursion in top-down approach) of this DP-table should be. Provided $g + h = k \leq n$ it is obvious that $dp(g, h, k, n, ?) = 2^k - 1$. As the question mark indicates, I don't understand what to do with the optional carrying bit in this case. I do not really understand how I should indicate there is no such sum, etc. Also, how to fill this DP-table? Should I use top-down approach? I need further help to proceed.

Answer 1

We are looking for a sum $z = x + y$, where $z$ has $k$ bits set, $x$ and $y$ have $g$ and $h$ bits set, and $z$ is as small as possible. We assume $g ≥ h$. A solution can be found directly, without any dynamic programming.

We add the numbers $x$ and $y$ from the lowest to the highest bit, taking carries into account. If we add two bits 0 + 0 without a carry, these bits can be removed without changing the number of bits set, but making the result smaller.

We can also take any pairs where we add 1 + 0 without carry, or 0 + 1 without carry, and move those pairs to the lowest bit positions. This doesn't change the number of bits set, but moving a 1 bit in the result to a lower bit position will not make the result larger, but may make it smaller.

Now if we add two bits 0 + 0 with carry, then we can remove these bits as well, but it is slightly more complicated. Obviously we can remove them if they are the highest bits. Otherwise, since adding 0 + 0 with or without carry does not produce a carry, and we removed all pairs 0 + 0 without carry, and moved all pairs 0 + 1 or 1 + 0 without carry to the lowest bit positions, the next higher bits must be 1 + 1. Adding 0 + 0 with carry gives a result of 1 and no carry, then adding 1 + 1 without carry gives a result of 0 with a carry. If we remove the two 0 bits, then we add 1 + 1 with carry, which gives a result of 1 with a carry. The number of bits set is unchanged, but a zero bit is removed in the result, making the result smaller.

So we are adding any number of pairs 0 + 1 or 1 + 0, then we may have a pair 1 + 1 producing a carry, followed by any number of pairs 1 + 1, 1 + 0 or 0 + 1. Starting with the addition 1+1 we will always have a carry, and adding 1 + 1 with carry produces a 1 with carry, while adding 1 + 0 or 0 + 1 with carry produces a 0 with carry. Reordering these pairs makes no difference to the number of bits set, but by moving all pairs 1 + 1 as far as possible to the lower positions we move 1-bits to lower positions in the result, making the result smaller.

Adding the initial 1+0 and 0+1 pairs produces exactly one bit set in the output for each bit set in the input. Adding 1+1 produces 0 output bits; each further pair produces one output bit set less than the input bits, and finally one bit will be set in the output from the final carry. If this optional range consists of j pairs, then we lose j output bits (for example, 111 + 111 = 1110, j = 3, six bits set in the input, 3 bits set in the output).

We see that we have no solution if $k > g + h$. If $k = g + h$ then one optimal solution is $x = (2^g - 1)·2^h$, y = (2^h - 1).

If $k < g + h$, then we let $j = (g + h) - k$. We need to lose exactly $j$ bits set, so the range of bit producing carries must be $j$ bits long. In this range, from j+1 to 2j bits are initially set; we get the smallest possible sum if we have as many pairs 1+1 as possible. If g + h ≤ j then there is no solution. We construct the numbers x, y as follows:

We have $a$ 1+1 pairs, where $a = min (k, j, h)$. Then we add $b = j-a$ pairs at higher and $c = k - a$ pairs at lower bit positions. Of these pairs, we have $g-a$ pairs 1+0, and $h-a$ pairs 0+1.

As an example: Let k = 10, g = 14, h = 3. j = 7, a = min (k, j, h) = min (10, 7, 3) = 3, b = j-a = 7-3 = 4, c = k - a = 10 - 3 = 7. We have

x =   1111 111 1111111
y =   0000 111 0000000
z = 1 0000 110 1111111

Answer 2

The subproblems are roughly: Given integers $g',h',k',n'$, find the smallest $n'$-bit integer of weight $k'$ which is the sum of integers of weights $g',h'$. Here $g' \leq g$, $h' \leq h$, $k' \leq k$, and $n' \leq n$. (You also need to worry about carry from the addition, which is where the roughly comes in.)