What is the next number having the same number of bit 1s?

Question

You are given a number, $A$, and you have to determine a number, $B$, such that $B>A$ and the number of $1's$ in the binary representation of $A =$ number of $1's$ in the binary representation of $B$.

What is the smallest $B$?

Answer 1

This problem actually shows up in the list of bit twiddling hacks as Next Permutation.

In C++:

t = A | (A - 1);
B = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(A) + 1)); 

__builtin_ctz(A) is the number of trailing zeros of A, or the largest power of 2 that divides A.

Going through the example in Rory's answer, if A == 011100, then:

t = A | (A - 1) = 011100 | 011011 = 011111

B = (t + 1) | (((~t & -~t) - 1) >> (__builtin_ctz(A) + 1))
  = (100000) | (((11111111 11100000 & 00000000 00100000) - 1) >> (2 + 1))
  = (100000) | (((100000 - 1) >> 3))
  = (100000) | (11111 >> 3)
  = (100000) | (11)
  = 100011

As a bit of explanation. Let's consider that A looks like:

X0[..1..][..0..]
     p      q

Where X are arbitrary bits followed by a 0, p 1s, and q 0s, where p > 0 but q doesn't have to be (in the original example, X is empty, p is 3, and q is 2). Given that, t is:

             t = X0[..1..][..1..]   // turn on all trailing bits of A
                      p      q

           t+1 = X1[..0..][..0..]
                      p      q

            ~t = Y1[..0..][..0..]  // where Y = ~X
                      p      q

    (~t & -~t) =  1[..0..][..0..]  // "freeze" the right-most 1-bit of ~t
                      p      q

(~t & -~t) - 1 =  0[..1..][..1..]
                      p      q

So when we rightshift that by __builtin_ctz(A) + 1, which is q+1:

((~t & -~t) - 1) >> (q + 1)
               =  [..1..]
                    p-1

Which, when |ed with `t+1:

             B = X1[..0..][..1..]
                     q+1    p-1

Which definitely solves the problem, given that we started with:

             A = X0[..1..][..0..]
                      p      q

Answer 2

If $A=0$, there is no such $B$. So let's assume that $A>0$.

Then the binary representation of $A$ is

$$A=Y01XO$$

where $Y$ is a series of digits, perhaps empty, $X$ is a series of $1$'s, perhaps empty, and $O$ is a series of $0$'s, perhaps empty. We can always find such a representation for positive $A$, though that may mean adding a $0$ to the front.

Then your answer is

$$B=Y10OX$$

Here is an example: If $A=011100$, then $B=100011$.

---

Here is a formula for the answer: Let $n$ be the largest integer such that $2^n \mid A$, and $m$ be the largest integer such that $2^m \mid (A+2^n)$. (In other words, if we say that the rightmost bit is position zero, the one before that one, and so on, then $n$ is the position of the rightmost $1$ in $A$'s binary expansion, while $m$ is the position of the rightmost zero up to position $n+1$. In the binary representation for $A$ above, $O$ has $n$ digits and $X$ has $m-n-1$ digits.) Then

$$B=A+2^n+2^{m-n-1}-1$$

Following through with @ccorn's comment, we can calculate this in C using C's bitwise and operator & if the computer uses two's complement arithmetic:

P2n = A & -A;
P2m = (A+P2n) & -(A+P2n);
B = A + P2n + (P2m / P2n) / 2 - 1;

I'm not sure what happens when $A$ has no next number. My guess is that $B$ is smallest of all numbers with that many $1$ bits.

Answer 3

Rewrite A as a binary signal ( a sequence of numbers in the set {0,1} ). Then perform a convolution with [1,-1]. The bits involved in the rightmost convolution which equates to -1 should be permuted with each other. This is to ensure the lowest value bit is switched to the lowest possible value upper bit. However we still need to minimize the remaining bits, the only way to do this is to count the number of 1s which are less significant than said switch bit and to put them at the lsb positions.

example 1: A = 101, conv(A,[1,-1],'valid') = 1,-1 B = 1(10) - bits in paren switched

For example, (as mentioned by Michael): 1(01)10 -> 1(10)01

---

To expand on ccorns discussion on C implementation, the above can be achieved as ((A>>1) & ~A) and count how many times we need to shift right for the lsb 1 to drop out. In the implementation we can add up the numbers of 1s in the low significant position as we go along with the shifting process above. Then we can just and (&) A by 0 for those positions and or (|) by $( (1 < cnt) - 1)$ which will be the trail of ones where cnt is the number of em.