Puede reformular el requisito:

• establezca N el número de bits que son diferentes al anterior (al iterar a través de los bits)
• si N=2 y el primer o último bit es 0 entonces la respuesta es sí
• si N=1 entonces la respuesta es sí (porque todos los 1 están en un lado)
• si N=0 entonces y cualquier bit es 0 entonces no tiene 1, depende de usted si considera que la respuesta es sí o no
• otra cosa: la respuesta es no

Pasar por todos los bits podría verse así:

 unsigned int count_bit_changes (uint32_t value) { unsigned int bit; unsigned int changes = 0; uint32_t last_bit = value & 1; for (bit = 1; bit < 32; bit++) { value = value >> 1; if (value & 1 != last_bit { changes++; last_bit = value & 1; } } return changes; }

Pero esto seguramente se puede optimizar (por ejemplo, abortando el bucle for cuando el value llega a 0 , lo que significa que no hay más bits significativos con valor 1 presentes).

Las CPU tienen instrucciones dedicadas para eso, muy rápido. En PC son BSR/BSF (introducidos en 80386 en 1985), en ARM son CLZ/CTZ

Use uno para encontrar el índice del bit de conjunto menos significativo, desplace el entero a la derecha en esa cantidad. Use otro para encontrar un índice del conjunto de bits más significativo, compare su número entero con (1u<<(bsr+1))-1.

Desafortunadamente, 35 años no fueron suficientes para actualizar el lenguaje C++ para que coincidiera con el hardware. Para usar estas instrucciones de C++, necesitará intrínsecos, estos no son portátiles y devuelven resultados en formatos ligeramente diferentes. Use el preprocesador, #ifdef , etc., para detectar el compilador y luego use los intrínsecos apropiados. En MSVC son _BitScanForward , _BitScanForward64 , _BitScanReverse , _BitScanReverse64 . En GCC y clang son __builtin_clz y __builtin_ctz .

De acuerdo, aquí hay una versión que recorre bits

 template<typename Integer> inline constexpr bool has_compact_bits(Integer val) noexcept { Integer test = 1; while(!(test & val) && test) test<<=1; // skip unset bits to find first set bit while( (test & val) && test) test<<=1; // skip set bits to find next unset bit while(!(test & val) && test) test<<=1; // skip unset bits to find an offending set bit return !test; }

Los primeros dos bucles encontraron la primera región compacta. El ciclo final verifica si hay algún otro bit establecido más allá de esa región.

La comparación con ceros en lugar de unos ahorrará algunas operaciones:

 bool has_compact_bits2(int val) { if (val == 0) return true; int h = __builtin_clz(val); // Clear bits to the left val = (unsigned)val << h; int l = __builtin_ctz(val); // Invert // >>l - Clear bits to the right return (~(unsigned)val)>>l == 0; }

Lo siguiente da como resultado una instrucción menos que la anterior en gcc10 -O3 en x86_64 y se usa en la extensión de signo:

 bool has_compact_bits3(int val) { if (val == 0) return true; int h = __builtin_clz(val); val <<= h; int l = __builtin_ctz(val); return ~(val>>l) == 0; }

Probado en Godbolt .

No estoy seguro de si es rápido, pero puede hacer una sola línea al verificar que val^(val>>1) tiene como máximo 2 bits activados.

Esto solo funciona con tipos sin signo: es necesario cambiar un 0 en la parte superior (cambio lógico), no un cambio aritmético a la derecha que cambia una copia del bit de signo.

 #include <bitset> bool has_compact_bits(unsigned val) { return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2; }

Para rechazar 0 (es decir, solo aceptar entradas que tengan exactamente 1 grupo de bits contiguo), AND lógico con val distinto de cero. Otras respuestas sobre esta pregunta aceptan 0 como compacto.

 bool has_compact_bits(unsigned val) { return std::bitset<8*sizeof(val)>((val ^ (val>>1))).count() <= 2 and val; }

C++ expone popcount de forma portátil a través de std::bitset::count() , o en C++20 a través de std::popcount . C todavía no tiene una forma portátil que se compile de manera confiable en un popcnt o instrucción similar en objetivos donde hay uno disponible.

En realidad, no es necesario contar los ceros a la izquierda. Como sugiere pmg en los comentarios, aprovechando el hecho de que los números que está buscando son los de la secuencia OEIS A023758 , es decir, los números de la forma 2^i - 2^j con i >= j , puede contar los ceros finales ( es decir , j - 1 ), alterne esos bits en el valor original (equivalente a agregar 2^j - 1 ), y luego verifique si ese valor tiene la forma 2^i - 1 . Con GCC/clang intrínsecos,

 bool has_compact_bits(int val) { if (val == 0) return true; // __builtin_ctz undefined if argument is zero int j = __builtin_ctz(val) + 1; val |= (1 << j) - 1; // add 2^j - 1 val &= (val + 1); // val set to zero if of the form (2^i - 1) return val == 0; }

Esta versión es un poco más rápida que la tuya y la propuesta por KamilCuk y la de Yuri Feldman solo con popcount.

Si está utilizando C++ 20, puede obtener una función portátil reemplazando __builtin_ctz con std::countr_zero :

 #include <bit> bool has_compact_bits(int val) { int j = std::countr_zero(static_cast<unsigned>(val)) + 1; // ugly cast val |= (1 << j) - 1; // add 2^j - 1 val &= (val + 1); // val set to zero if of the form (2^i - 1) return val == 0; }

El molde es feo, pero le advierte que es mejor trabajar con tipos sin firmar al manipular bits. Las alternativas anteriores a C++20 son boost::multiprecision::lsb .

Editar:

El punto de referencia en el enlace tachado estaba limitado por el hecho de que no se había emitido ninguna instrucción popcount para la versión de Yuri Feldman. Intentando compilarlos en mi PC con -march=westmere , he medido el siguiente tiempo para mil millones de iteraciones con secuencias idénticas de std::mt19937 :

• tu versión: 5.7 s
• Segunda versión de KamilCuk: 4.7 s
• mi versión: 4.7 s
• Primera versión de Eric Postpischil: 4.3 s
• Versión de Yuri Feldman (usando explícitamente __builtin_popcount ): 4.1 s

Entonces, al menos en mi arquitectura, el más rápido parece ser el que tiene popcount.

Edición 2:

He actualizado mi benchmark con la nueva versión de Eric Postpischil. Como se solicitó en los comentarios, el código de mi prueba se puede encontrar aquí . He agregado un ciclo sin operación para estimar el tiempo que necesita el PRNG. También he añadido las dos versiones de KevinZ. El código se ha compilado en clang con -O3 -msse4 -mbmi para obtener instrucciones popcnt y blsi (gracias a Peter Cordes).

Resultados: Al menos en mi arquitectura, la versión de Eric Postpischil es exactamente tan rápida como la de Yuri Feldman, y al menos dos veces más rápida que cualquier otra versión propuesta hasta ahora.

Puede hacer esta secuencia de cálculos (suponiendo que val sea una entrada):

 uint32_t x = val; x |= x >> 1; x |= x >> 2; x |= x >> 4; x |= x >> 8; x |= x >> 16;

para obtener un número con todos ceros debajo del 1 más significativo lleno de unos.

También puede calcular y = val & -val para quitar todo excepto el bit menos significativo de 1 en val (por ejemplo, 7 & -7 == 1 y 12 & -12 == 4 ).
Advertencia: esto fallará para val == INT_MIN , por lo que deberá manejar este caso por separado, pero esto es inmediato.

Luego, desplace y a la derecha una posición, para estar un poco por debajo del LSB real de val , y realice la misma rutina que para x :

 uint32_t y = (val & -val) >> 1; y |= y >> 1; y |= y >> 2; y |= y >> 4; y |= y >> 8; y |= y >> 16;

Entonces x - y o x & ~y o x ^ y produce la máscara de bits 'compacta' que abarca toda la longitud de val . Simplemente compárelo con val para ver si val es 'compacto'.

Solución:

 static _Bool IsCompact(unsigned x) { return (x & x + (x & -x)) == 0; }

Brevemente:

x & -x da el conjunto de bits más bajo en x (o cero si x es cero).

x + (x & -x) convierte la cadena más baja de 1 consecutivos en un solo 1 más alto (o se ajusta a cero).

x & x + (x & -x) borra esos 1 bits.

(x & x + (x & -x)) == 0 comprueba si quedan otros 1 bits.

Más extenso:

-x es igual a ~x+1 (para el int en la pregunta, asumimos el complemento a dos, pero es preferible que no tenga unsigned ). Después de que los bits se invierten en ~x , agregar 1 lleva de modo que retrocede los bits 1 bajos en ~x y el primer bit 0, pero luego se detiene. Por lo tanto, los bits bajos de -x hasta su primer 1 incluido son los mismos que los bits bajos de x , pero todos los bits superiores se invierten. (Ejemplo: ~10011100 da 01100011 , y sumando 1 da 01100100 , por lo que los 100 bajos son los mismos, pero los 10011 altos se invierten en 01100 ). Entonces x & -x nos da el único bit que es 1 en ambos, que es ese bit más bajo ( 00000100 ). (Si x es cero, x & -x es cero).

Agregar esto a x provoca un acarreo a través de todos los 1 consecutivos, cambiándolos a 0. Dejará un 1 en el siguiente bit 0 más alto (o continuará hasta el extremo superior, dejando un total envuelto de cero) ( 10100000 .)

Cuando se hace AND con x , hay 0 en los lugares donde los 1 se cambiaron a 0 (y también donde el acarreo cambió un 0 a un 1). Entonces, el resultado no es cero solo si hay otro 1 bit más arriba.

En realidad, no hay necesidad de usar ningún intrínseco.

Primero voltea todos los 0 antes del primer 1. Luego prueba si el nuevo valor es un número de Mersenne. En este algo, cero se asigna a verdadero.

 bool has_compact_bits( unsigned const x ) { // fill up the low order zeroes unsigned const y = x | ( x - 1 ); // test if the 1's is one solid block return not ( y & ( y + 1 ) ); }

Por supuesto, si quiere usar intrínsecos, aquí está el método popcount:

 bool has_compact_bits( unsigned const x ) { size_t const num_bits = CHAR_BIT * sizeof(unsigned); size_t const sum = __builtin_ctz(x) + __builtin_popcount(x) + __builtin_clz(z); return sum == num_bits; }

Podemos hacer uso de las instrucciones integradas de gcc para verificar si:

El conteo de bits establecidos

int __builtin_popcount (int x sin signo)
Devuelve el número de bits de 1 en x.

es igual a (a - b):

a : Índice del bit más alto establecido (32 - CTZ) (32 porque 32 bits en un entero sin signo).

int __builtin_clz (int x sin signo)
Devuelve el número de bits 0 iniciales en x, comenzando en la posición de bit más significativa. Si x es 0, el resultado es indefinido.

b : Índice del bit más bajo establecido (CLZ):

int __builtin_clz (int x sin signo)
Devuelve el número de bits 0 iniciales en x, comenzando en la posición de bit más significativa. Si x es 0, el resultado es indefinido.

Por ejemplo si n = 0b0001100110; obtendremos 4 con popcount pero la diferencia de índice (a - b) devolverá 6.

 bool has_contiguous_one_bits(unsigned n) { return (32 - __builtin_clz(n) - __builtin_ctz(n)) == __builtin_popcount(n); }

que también se puede escribir como:

 bool has_contiguous_one_bits(unsigned n) { return (__builtin_popcount(n) + __builtin_clz(n) + __builtin_ctz(n)) == 32; }

No creo que sea más elegante o eficiente que la respuesta actual más votada:

 return (x & x + (x & -x)) == 0;

con el siguiente montaje:

 mov eax, edi neg eax and eax, edi add eax, edi test eax, edi sete al

pero es probablemente más fácil de entender.