operador - rotacion de bits en c
¿Cómo encontrar la posición del bit único-set en un valor de 64 bits utilizando la manipulación de bits de manera eficiente? (9)
Solo digo que tengo un valor de tipo uint64_t visto como una secuencia de octetos (1 octeto = 8 bits). Se uint64_t valor uint64_t contiene solo un bit configurado en una posición MSB. Por lo tanto, el valor de uint64_t puede estar en una de las siguientes representaciones binarias:
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7
00000000 00000000 00000000 00000000 00000000 00000000 10000000 00000000 pos = 15
00000000 00000000 00000000 00000000 00000000 10000000 00000000 00000000 pos = 23
00000000 00000000 00000000 00000000 10000000 00000000 00000000 00000000 pos = 31
00000000 00000000 00000000 10000000 00000000 00000000 00000000 00000000 pos = 39
00000000 00000000 10000000 00000000 00000000 00000000 00000000 00000000 pos = 47
00000000 10000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 55
10000000 00000000 00000000 00000000 00000000 00000000 00000000 00000000 pos = 63
Necesito una función rápida que devuelva la posición del bit establecido , pero devuelve 0 si no hay ningún bit configurado.
Si es posible, lo quiero sin bucle ni ramificación.
00000000 00000000 00000000 00000000 00000000 00000000 00000000 10000000 pos = 7..., pero devuelve 0 si no hay ningún bit configurado.
Esto devolverá lo mismo si se establece el primer bit o ningún bit; sin embargo, en x86_64, eso es exactamente lo que hace bsrq:
int bsrq_x86_64(uint64_t x){
int ret;
asm("bsrq %0, %1":"=r"(ret):"r"(x));
return ret;
}
Sin embargo; si el primer bit está configurado, también devolverá 0; aquí hay un método que se ejecutará en tiempo constante (sin bucles o bifurcaciones) y devuelve -1 cuando no se establecen bits (para distinguirlo de cuando se establece el primer bit).
int find_bit(unsigned long long x){
int ret=0,
cmp = (x>(1LL<<31))<<5; //32 if true else 0
ret += cmp;
x >>= cmp;
cmp = (x>(1<<15))<<4; //16 if true else 0
ret += cmp;
x >>= cmp;
cmp = (x>(1<<7))<<3; //8
ret += cmp;
x >>= cmp;
cmp = (x>(1<<3))<<2; //4
ret += cmp;
x >>= cmp;
cmp = (x>(1<<1))<<1; //2
ret += cmp;
x >>= cmp;
cmp = (x>1);
ret += cmp;
x >>= cmp;
ret += x;
return ret-1;
}
Técnicamente, esto solo devuelve la posición del bit establecido más significativo. Dependiendo del tipo de flotador utilizado, esto se puede hacer en menos operaciones usando el cuadrado inverso rápido u otro truco de twiddling de bits
Por cierto, si no te importa usar compilaciones compiladas, puedes hacer:
__builtin_popcountll(n-1) o __builtin_ctzll(n) o __builtin_ffsll(n)-1
Aquí hay una solución portátil, que, sin embargo, será más lenta que las soluciones que aprovechan las instrucciones especializadas como clz (contar ceros a la izquierda). Agregué comentarios en cada paso del algoritmo que explican cómo funciona.
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
uint64_t t, c;
t = a - 1; // create mask
c = t >> 63; // correction for zero inputs
t = t + c; // apply zero correction if necessary
t = t & 0x0101010101010101ULL; // mark each byte covered by mask
t = t * 0x0101010101010101ULL; // sum the byte markers in uppermost byte
t = (t >> 53) - 1; // retrieve count and diminish by 1 for bit position
t = t + c; // apply zero correction if necessary
return (int)t;
}
int main (void)
{
int i;
uint64_t a;
a = 0;
printf ("a=%016llx bit_pos=%2d reference_pos=%2d/n", a, bit_pos(a), 0);
for (i = 7; i < 64; i += 8) {
a = (1ULL << i);
printf ("a=%016llx bit_pos=%2d reference_pos=%2d/n",
a, bit_pos(a), i);
}
return EXIT_SUCCESS;
}
La salida de este código debería verse así:
a=0000000000000000 bit_pos= 0 reference_pos= 0
a=0000000000000080 bit_pos= 7 reference_pos= 7
a=0000000000008000 bit_pos=15 reference_pos=15
a=0000000000800000 bit_pos=23 reference_pos=23
a=0000000080000000 bit_pos=31 reference_pos=31
a=0000008000000000 bit_pos=39 reference_pos=39
a=0000800000000000 bit_pos=47 reference_pos=47
a=0080000000000000 bit_pos=55 reference_pos=55
a=8000000000000000 bit_pos=63 reference_pos=63
En una plataforma x86_64, mi compilador traduce bit_pos() en este código de máquina:
bit_pos PROC
lea r8, QWORD PTR [-1+rcx]
shr r8, 63
mov r9, 0101010101010101H
lea rdx, QWORD PTR [-1+r8+rcx]
and rdx, r9
imul r9, rdx
shr r9, 53
lea rax, QWORD PTR [-1+r8+r9]
ret
[Actualización posterior]
La respuesta de Duskwuff me dejó claro que mi pensamiento original era innecesariamente intrincado. De hecho, utilizando el enfoque de duskwuff, la funcionalidad deseada se puede expresar mucho más concisa de la siguiente manera:
/* return position of set bit, if exactly one of bits n*8-1 is set; n in [1,8]
return 0 if no bit is set
*/
int bit_pos (uint64_t a)
{
const uint64_t magic_multiplier =
(( 7ULL << 56) | (15ULL << 48) | (23ULL << 40) | (31ULL << 32) |
(39ULL << 24) | (47ULL << 16) | (55ULL << 8) | (63ULL << 0));
return (int)(((a >> 7) * magic_multiplier) >> 56);
}
Cualquier compilador razonable precalculará el multiplicador mágico, que es 0x070f171f272f373fULL . El código emitido para un objetivo x86_64 se reduce a
bit_pos PROC
mov rax, 070f171f272f373fH
shr rcx, 7
imul rax, rcx
shr rax, 56
ret
El hardware moderno tiene instrucciones especializadas para eso (LZCNT, TZCNT en procesadores Intel).
La mayoría de los compiladores tienen intrínsecos para generarlos fácilmente. Vea la siguiente página de wikipedia .
El valor mod 0x8C produce un valor único para cada uno de los casos.
Este valor de mod 0x11 sigue siendo único.
El segundo valor en la tabla es el mod resultante 0x11.
128 9
32768 5
8388608 10
2147483648 0
549755813888 14
140737488355328 2
36028797018963968 4
9223372036854775808 15
Entonces una simple tabla de búsqueda será suficiente.
int find_bit(uint64_t bit){
int lookup[] = { the seventeen values };
return lookup[ (bit % 0x8C) % 0x11];
}
Sin ramificaciones, sin trucos de compilación.
Para completar, la matriz es
{ 31, 0, 47, 15, 55, 0, 0, 7, 23, 0, 0, 0, 39, 63, 0, 0}
Multiplique el valor por una constante de 64 bits cuidadosamente diseñada, luego enmascare los 4 bits superiores. Para cualquier CPU con multiplicación rápida de 64 bits, esto es probablemente lo más óptimo que se puede obtener.
int field_set(uint64_t input) {
uint64_t field = input * 0x20406080a0c0e1ULL;
return (field >> 60) & 15;
}
// field_set(0x0000000000000000ULL) = 0
// field_set(0x0000000000000080ULL) = 1
// field_set(0x0000000000008000ULL) = 2
// field_set(0x0000000000800000ULL) = 3
// field_set(0x0000000080000000ULL) = 4
// field_set(0x0000008000000000ULL) = 5
// field_set(0x0000800000000000ULL) = 6
// field_set(0x0080000000000000ULL) = 7
// field_set(0x8000000000000000ULL) = 8
clang implementa esto en tres instrucciones x86_64, sin contar la configuración y limpieza del marco:
_field_set:
push %rbp
mov %rsp,%rbp
movabs $0x20406080a0c0e1,%rax
imul %rdi,%rax
shr $0x3c,%rax
pop %rbp
retq
Tenga en cuenta que los resultados para cualquier otra entrada serán bastante aleatorios. (Entonces no hagas eso)
No creo que haya ninguna forma factible de extender este método para devolver valores en el rango 7..63 directamente (la estructura de la constante no lo permite), pero puede convertir los resultados a ese rango multiplicando el resultado por 7.
Con respecto a cómo se diseñó esta constante: comencé con las siguientes observaciones:
- La multiplicación sin signo es una operación rápida en la mayoría de las CPU, y puede tener efectos útiles. Deberíamos usarlo :)
- Multiplicando cualquier cosa por cero da como resultado cero. Dado que esto coincide con el resultado deseado para una entrada sin conjuntos de bits, hasta ahora nos está yendo bien.
- Multiplicar cualquier cosa por
1ULL<<63(es decir, su valor "pos = 63") solo puede dar como resultado el mismo valor, o cero. (No es posible que tenga ningún conjunto de bits inferior, y no hay bits más altos que modificar). Por lo tanto, debemos encontrar la forma de tratar este valor como el resultado correcto. - Una forma conveniente de hacer que este valor sea su propio resultado correcto es desplazándolo a la derecha en 60 bits. Esto lo cambia a "8", que es una representación bastante conveniente. Podemos proceder a codificar las otras salidas como 1 a 7.
Multiplicar nuestra constante por cada uno de los otros campos de bit es equivalente a desplazar hacia la izquierda un número de bits igual a su "posición". El desplazamiento a la derecha en 60 bits hace que solo los 4 bits a la izquierda de una posición determinada aparezcan en el resultado. Por lo tanto, podemos crear todos los casos, excepto uno de la siguiente manera:
uint64_t constant = ( 1ULL << (60 - 7) | 2ULL << (60 - 15) | 3ULL << (60 - 23) | 4ULL << (60 - 31) | 5ULL << (60 - 39) | 6ULL << (60 - 47) | 7ULL << (60 - 55) );
Hasta ahora, la constante es 0x20406080a0c0e0ULL . Sin embargo, esto no da el resultado correcto para pos=63 ; esta constante es par, por lo que multiplicarla por esa entrada da cero. Debemos establecer el bit más bajo (es decir, constant |= 1ULL ) para que funcione el caso, lo que nos da el valor final de 0x20406080a0c0e1ULL .
Tenga en cuenta que la construcción anterior se puede modificar para codificar los resultados de manera diferente. Sin embargo, la salida de 8 se fija como se describió anteriormente, y todas las demás salidas deben caber en 4 bits (es decir, de 0 a 15).
Se eliminó la etiqueta C ++, pero aquí hay una respuesta portátil de C ++, ya que puedes compilarla con C ++ y usar una interfaz extern C externa:
Si tienes una potencia de 2 y restas, terminas con un número binario con la cantidad de bits configurados igual a la posición
Una forma de contar el número de bits configurados ( 1 s binario) está empaquetada, presumiblemente más eficientemente por cada implementación del stl, en el count funciones del miembro std::bitset
Tenga en cuenta que su especificación ha devuelto 0 para 0 o 1 , así que agregué as_specified_pos para cumplir este requisito. Personalmente, simplemente lo dejaría devolver el valor natural de 64 cuando pase 0 para poder diferenciar, y para la velocidad.
El siguiente código debe ser extremadamente portátil y muy probablemente optimizado por plataforma por los vendedores del compilador:
#include <bitset>
uint64_t pos(uint64_t val)
{
return std::bitset<64>(val-1).count();
}
uint64_t as_specified_pos(uint64_t val)
{
return (val) ? pos(val) : 0;
}
En Linux con g ++ obtengo el siguiente código desensamblado:
0000000000000000 <pos(unsigned long)>:
0: 48 8d 47 ff lea -0x1(%rdi),%rax
4: f3 48 0f b8 c0 popcnt %rax,%rax
9: c3 retq
a: 66 0f 1f 44 00 00 nopw 0x0(%rax,%rax,1)
0000000000000010 <as_specified_pos(unsigned long)>:
10: 31 c0 xor %eax,%eax
12: 48 85 ff test %rdi,%rdi
15: 74 09 je 20 <as_specified_pos(unsigned long)+0x10>
17: 48 8d 47 ff lea -0x1(%rdi),%rax
1b: f3 48 0f b8 c0 popcnt %rax,%rax
20: f3 c3 repz retq
Si desea un algoritmo para el trabajo en lugar de un built-in, esto lo hará. Proporciona el número de bits del bit más significativo de 1 bit, incluso si se establece más de un bit. Se estrecha la posición al dividir iterativamente el rango de bits bajo consideración en mitades, probando si hay bits establecidos en la mitad superior, tomando esa mitad como el nuevo rango de bits si es así, y tomando la mitad inferior como el nuevo rango de bits .
#define TRY_WINDOW(bits, n, msb) do { /
uint64_t t = n >> bits; /
if (t) { /
msb += bits; /
n = t; /
} /
} while (0)
int msb(uint64_t n) {
int msb = 0;
TRY_WINDOW(32, n, msb);
TRY_WINDOW(16, n, msb);
TRY_WINDOW( 8, n, msb);
TRY_WINDOW( 4, n, msb);
TRY_WINDOW( 2, n, msb);
TRY_WINDOW( 1, n, msb);
return msb;
}
Si puede usar POSIX, use la función strings.h ( ffs() de strings.h (no string.h !). Devuelve la posición del conjunto de bits menos significativo (uno indexado) o un cero si el argumento es cero. En la mayoría de las implementaciones, una llamada a ffs() está en línea y compilada en la instrucción de máquina correspondiente, como bsf en x86. El glibc también tiene ffsll() para argumentos long long que deberían ser aún más adecuados para su problema si está disponible.
Una simple solución de búsqueda. m=67 es el número entero más pequeño para el cual los valores (1<<k)%m son todos distintos, for k<m . Con (código transponible python):
lut = [-1]*67
for i in range(0,64) : lut[(1<<i)%67] = i
Entonces lut[a%67] da k si a = 1<<k . -1 valores no utilizados.