¿Cuál es el siguiente número con el mismo número de bits 1s?

Question

Se le dará un número, $A$, y usted tiene que determinar un número, $B$, de tal manera que $B>A$ y el número de $1's$ en la representación binaria de $A =$ número de $1's$ en la representación binaria de $B$.

¿Cuál es la menor $B$?

Answer 1

Si $A=0$, no se $B$. Así que vamos a suponer que $A>0$.

A continuación, la representación binaria de $A$ es

$$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 $Un$, 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 \mediados de los 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 2

Este problema se muestra en la lista de bits con los hacks como la Siguiente Permutación.

En C++:

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

__builtin_ctz(A) es el número de ceros a la derecha de la A, o la mayor potencia de 2 que divide A.

Pasando por el ejemplo de Rory la respuesta, si A == 011100, entonces:

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

Como un poco de explicación. Vamos a considerar que A parece:

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

Donde X son arbitrarias bits seguido por un 0, p 1 y q 0, donde p > 0 pero q no tiene que ser (en el ejemplo original, X está vacía, p es 3, y q 2). Dado que, t está:

             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

Así que cuando nos rightshift que por __builtin_ctz(A) + 1, que es q+1:

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

Que, cuando |ed con `t+1:

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

Lo que sin duda se soluciona el problema, dado que empezamos con:

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

Answer 3

Reescribir como una señal binaria ( una secuencia de números en el conjunto {0,1} ). Luego de realizar una convolución con [1,-1]. Los bits que participan en el extremo derecho de la convolución, lo que equivale a -1 debe ser permutada el uno con el otro. Esto es para asegurar que el valor más bajo de bits es cambiado al valor más bajo posible superior de bits. Sin embargo todavía tenemos que minimizar el resto de los bits, la única manera de hacerlo es contar el número de 1s que son menos importantes que dijo conmutador de bits y ponerlos en la lsb posiciones.

ejemplo 1: A = 101, conv(A,[1,-1],'válida') = 1,-1 B = 1(10) - bits en el paréntesis de conmutación

Por ejemplo, (como lo menciona Michael): 1(01)10 -> 1(10)01

---

Para ampliar ccorns discusión sobre la implementación en C, lo anterior puede lograrse, como ((A>>1) & ~A) y contar cuántas veces tenemos que desplazar a la derecha de la lsb 1 de deserción. En la aplicación podemos añadir el número de 1s en la baja posición significativa a medida que avanzamos con el proceso de desplazamiento de arriba. A continuación, podemos y (&) por 0 para esas posiciones y o (|) por $( (1 < cnt) - 1)$ que será el camino de aquellos en los que la cnt es el número de em.