int subtractone(int x) { int f = 1; // Flip all the set bits until we find a 1 at position y while (!(x & f)) { x = x^f; f <<= 1; } return x^f; // return answer but remember to flip the 1 at y }

Puede hacerlo con operaciones bit a bit usando lo anterior, y solo tiene que dividir su número entero en partes de 8 bits para enviar 8 veces a esta función. La siguiente parte fue tomada de ¿Cómo dividir un número de 64 bits en ocho valores de 8 bits? conmigo agregando la función anterior

 uint64_t v= _64bitVariable; uint8_t i=0,parts[8]={0}; do parts[i++] = subtractone(v&0xFF); while (v>>=8);

Es C o C ++ válido independientemente de cómo alguien encuentre esto

Señalaría que el código que ha escrito en realidad se vectoriza una vez que comienza a tratar con más de un solo uint64_t.

https://godbolt.org/z/J9DRzd

No estoy seguro de si esto es lo que quieres, pero hace las 8 restas en paralelo entre sí:

 #include <cstdint> constexpr uint64_t mask = 0x0101010101010101; uint64_t sub(uint64_t arg) { uint64_t mask_cp = mask; for(auto i = 0; i < 8 && mask_cp; ++i) { uint64_t new_mask = (arg & mask_cp) ^ mask_cp; arg = arg ^ mask_cp; mask_cp = new_mask << 1; } return arg; }

Explicación: la máscara de bits comienza con un 1 en cada uno de los números de 8 bits. Lo solucionamos con nuestro argumento. Si tuviéramos un 1 en este lugar, restamos 1 y tenemos que parar. Esto se hace configurando el bit correspondiente a 0 en new_mask. Si tuviéramos un 0, lo ponemos a 1 y tenemos que hacer el acarreo, así que el bit se queda en 1 y cambiamos la máscara a la izquierda. Será mejor que compruebes por ti mismo si la generación de la nueva máscara funciona según lo previsto, creo que sí, pero una segunda opinión no estaría mal.

PD: En realidad, no estoy seguro de si la verificación de mask_cp no es nula en el bucle y puede ralentizar el programa. Sin él, el código seguiría siendo correcto (ya que la máscara 0 simplemente no hace nada) y sería mucho más fácil para el compilador desenrollar bucles.

Si tiene una CPU con instrucciones SIMD eficientes, SSE/MMX paddb ( _mm_add_epi8 ) también es viable. La respuesta de Peter Cordes también describe la sintaxis del vector GNU C (gcc/clang) y la seguridad para UB de alias estricto. Recomiendo encarecidamente revisar esa respuesta también.

Hacerlo usted mismo con uint64_t es completamente portátil, pero aún requiere cuidado para evitar problemas de alineación y UB de alias estricto al acceder a una matriz uint8_t con uint64_t* . Dejó esa parte fuera de la pregunta al comenzar con sus datos en un uint64_t ya, pero para GNU C, may_alias typedef resuelve el problema (vea la respuesta de Peter para eso o memcpy ).

De lo contrario, podría asignar/declarar sus datos como uint64_t y acceder a ellos a través uint8_t* cuando desee bytes individuales. unsigned char* puede crear un alias de cualquier cosa, de modo que elude el problema para el caso específico de los elementos de 8 bits. (Si uint8_t existe, probablemente sea seguro asumir que es un unsigned char ).

Tenga en cuenta que este es un cambio de un algoritmo incorrecto anterior (consulte el historial de revisiones).

Esto es posible sin bucles para restas arbitrarias y se vuelve más eficiente para una constante conocida como 1 en cada byte. El truco principal es evitar el acarreo de cada byte configurando el bit alto y luego corregir el resultado de la resta.

Vamos a optimizar ligeramente la técnica de resta dada aquí . Ellos definen:

 SWAR sub z = x - y z = ((x | H) - (y &~H)) ^ ((x ^~y) & H)

con H definido como 0x8080808080808080U (es decir, los MSB de cada entero empaquetado). Para un decremento, y es 0x0101010101010101U .

Sabemos que y tiene todos sus MSB despejados, por lo que podemos omitir uno de los pasos de la máscara (es decir y & ~H es lo mismo que y en nuestro caso). El cálculo procede de la siguiente manera:

1. Establecemos los MSB de cada componente de x en 1, de modo que un préstamo no se pueda propagar más allá del MSB al siguiente componente. Llame a esto la entrada ajustada.
2. Restamos 1 de cada componente, restando 0x01010101010101 de la entrada corregida. Esto no provoca préstamos entre componentes gracias al paso 1. Llame a esto la salida ajustada.
3. Necesitamos ahora corregir el MSB del resultado. Hacemos xor en la salida ajustada con los MSB invertidos de la entrada original para terminar de arreglar el resultado.

La operación se puede escribir como:

 #define U64MASK 0x0101010101010101U #define MSBON 0x8080808080808080U uint64_t decEach(uint64_t i){ return ((i | MSBON) - U64MASK) ^ ((i ^ MSBON) & MSBON); }

Preferiblemente, el compilador lo inserta en línea (utilice las directivas del compilador para forzar esto), o la expresión se escribe en línea como parte de otra función.

Casos de prueba:

 in: 0000000000000000 out: ffffffffffffffff in: f200000015000013 out: f1ffffff14ffff12 in: 0000000000000100 out: ffffffffffff00ff in: 808080807f7f7f7f out: 7f7f7f7f7e7e7e7e in: 0101010101010101 out: 0000000000000000

Detalles de rendimiento

Aquí está el ensamblado x86_64 para una única invocación de la función. Para un mejor rendimiento, debe alinearse con la esperanza de que las constantes puedan vivir en un registro el mayor tiempo posible. En un ciclo cerrado donde las constantes viven en un registro, el decremento real requiere cinco instrucciones: o+no+y+agregar+xor después de la optimización. No veo alternativas que superen la optimización del compilador.

 uint64t[rax] decEach(rcx): movabs rcx, -9187201950435737472 mov rdx, rdi or rdx, rcx movabs rax, -72340172838076673 add rax, rdx and rdi, rcx xor rdi, rcx xor rax, rdi ret

Con algunas pruebas de IACA del siguiente fragmento:

 // Repeat the SWAR dec in a loop as a microbenchmark uint64_t perftest(uint64_t dummyArg){ uint64_t dummyCounter = 0; uint64_t i = 0x74656a6d27080100U; // another dummy value. while(i ^ dummyArg) { IACA_START uint64_t naive = i - U64MASK; i = naive + ((i ^ naive ^ U64MASK) & U64MASK); dummyCounter++; } IACA_END return dummyCounter; }

podemos demostrar que en una máquina Skylake, realizar el decremento, xor y comparar+saltar se puede realizar en poco menos de 5 ciclos por iteración:

 Throughput Analysis Report -------------------------- Block Throughput: 4.96 Cycles Throughput Bottleneck: Backend Loop Count: 26 Port Binding In Cycles Per Iteration: -------------------------------------------------------------------------------------------------- | Port | 0 - DV | 1 | 2 - D | 3 - D | 4 | 5 | 6 | 7 | -------------------------------------------------------------------------------------------------- | Cycles | 1.5 0.0 | 1.5 | 0.0 0.0 | 0.0 0.0 | 0.0 | 1.5 | 1.5 | 0.0 | --------------------------------------------------------------------------------------------------

(Por supuesto, en x86-64 simplemente cargaría o movq en un registro XMM para paddb , por lo que podría ser más interesante ver cómo se compila para un ISA como RISC-V).

Concéntrese en trabajar en cada byte completamente solo, luego vuelva a colocarlo donde estaba.

 uint64_t sub(uint64_t arg) { uint64_t res = 0; for (int i = 0; i < 64; i+=8) res += ((arg >> i) - 1 & 0xFFU) << i; return res; }

Puede asegurarse de que la resta no se desborde y luego arreglar el bit alto:

 uint64_t sub(uint64_t arg) { uint64_t x1 = arg | 0x80808080808080; uint64_t x2 = ~arg & 0x80808080808080; // or uint64_t x2 = arg ^ x1; to save one instruction if you don't have an andnot instruction return (x1 - 0x101010101010101) ^ x2; }

Para RISC-V, probablemente esté usando GCC/clang.

Dato curioso: GCC conoce algunos de estos trucos de SWAR bithack (que se muestran en otras respuestas) y puede usarlos para usted al compilar código con vectores nativos GNU C para objetivos sin instrucciones SIMD de hardware. (Pero clang para RISC-V simplemente lo desplegará ingenuamente en operaciones escalares, por lo que debe hacerlo usted mismo si desea un buen rendimiento en todos los compiladores).

Una ventaja de la sintaxis de vectores nativos es que cuando se dirige a una máquina con SIMD de hardware, lo usará en lugar de vectorizar automáticamente su bithack o algo horrible como eso.

Hace que sea fácil escribir vector -= scalar ; la sintaxis Just Works, transmitiendo implícitamente, también conocido como splatting the escalar para usted.

También tenga en cuenta que una carga de uint64_t* desde una uint8_t array[] es UB de alias estricto, así que tenga cuidado con eso. (Consulte también ¿Por qué strlen de glibc necesita ser tan complicado para ejecutarse rápidamente? Re: hacer que los bithacks de SWAR sean seguros en C puro). Es posible que desee algo como esto para declarar un uint64_t que puede apuntar para acceder a cualquier otro objeto, como cómo funciona char* en ISO C / C ++.

utilícelos para obtener datos de uint8_t en un uint64_t para usarlos con otras respuestas:

 // GNU C: gcc/clang/ICC but not MSVC typedef uint64_t aliasing_u64 __attribute__((may_alias)); // still requires alignment typedef uint64_t aliasing_unaligned_u64 __attribute__((may_alias, aligned(1)));

La otra forma de realizar cargas seguras con alias es con memcpy en un uint64_t , que también elimina el requisito de alineación alignof(uint64_t ). Pero en ISA sin cargas no alineadas eficientes, gcc/clang no se alinea y optimiza memcpy cuando no pueden probar que el puntero está alineado, lo que sería desastroso para el rendimiento.

TL: DR: su mejor apuesta es declarar sus datos como uint64_t array[...] o asignarlos dinámicamente como uint64_t , o preferiblemente alignas(16) uint64_t array[]; Eso asegura la alineación de al menos 8 bytes, o 16 si especifica alignas .

Dado que uint8_t es casi con certeza unsigned char* , es seguro acceder a los bytes de un uint64_t a través de uint8_t* (pero no viceversa para una matriz uint8_t). Entonces, para este caso especial en el que el tipo de elemento estrecho es unsigned char , puede eludir el problema del alias estricto porque char es especial.

Ejemplo de sintaxis de vector nativo GNU C:

Los vectores nativos de GNU C siempre pueden crear alias con su tipo subyacente (p. ej., int int __attribute__((vector_size(16))) puede crear alias de forma segura pero no float o uint8_t o cualquier otra cosa.

 #include <stdint.h> #include <stddef.h> // assumes array is 16-byte aligned void dec_mem_gnu(uint8_t *array) { typedef uint8_t v16u8 __attribute__ ((vector_size (16), may_alias)); v16u8 *vecs = (v16u8*) array; vecs[0] -= 1; vecs[1] -= 1; // can be done in a loop. }

Para RISC-V sin HW SIMD, podría usar vector_size(8) para expresar solo la granularidad que puede usar de manera eficiente y hacer el doble de vectores más pequeños.

Pero vector_size(8) compila muy estúpidamente para x86 con GCC y clang: GCC usa bithacks SWAR en registros de enteros GP, clang desempaqueta elementos de 2 bytes para llenar un registro XMM de 16 bytes y luego vuelve a empaquetar. (MMX es tan obsoleto que GCC/clang ni siquiera se molestan en usarlo, al menos no para x86-64).

Pero con vector_size (16) ( Godbolt ) obtenemos el movdqa / paddb . (Con un vector de todos unos generado por pcmpeqd same,same ). Con -march=skylake todavía obtenemos dos operaciones XMM separadas en lugar de una YMM, por lo que, lamentablemente, los compiladores actuales tampoco "auto-vectorizan" las operaciones vectoriales en vectores más amplios:/

Para AArch64, no es tan malo usar vector_size(8) ( Godbolt ); ARM/AArch64 puede funcionar de forma nativa en fragmentos de 8 o 16 bytes con registros d o q .

Por lo tanto, probablemente desee vector_size(16) si desea un rendimiento portátil en x86, RISC-V, ARM/AArch64 y POWER . Sin embargo, algunas otras ISA hacen SIMD dentro de registros enteros de 64 bits, como MIPS MSA, creo.

vector_size(8) hace que sea más fácil mirar el asm (solo un registro de datos): explorador del compilador Godbolt

 # GCC8.2 -O3 for RISC-V for vector_size(8) and only one vector dec_mem_gnu(unsigned char*): lui a4,%hi(.LC1) # generate address for static constants. ld a5,0(a0) # a5 = load from function arg ld a3,%lo(.LC1)(a4) # a3 = 0x7F7F7F7F7F7F7F7F lui a2,%hi(.LC0) ld a2,%lo(.LC0)(a2) # a2 = 0x8080808080808080 # above here can be hoisted out of loops not a4,a5 # nx = ~x and a5,a5,a3 # x &= 0x7f... clear high bit and a4,a4,a2 # nx = (~x) & 0x80... inverse high bit isolated add a5,a5,a3 # x += 0x7f... (128-1) xor a5,a4,a5 # x ^= nx restore high bit or something. sd a5,0(a0) # store the result ret

Creo que es la misma idea básica que las otras respuestas sin bucle; previniendo el acarreo y luego arreglando el resultado.

Estas son 5 instrucciones ALU, peor que la respuesta principal, creo. Pero parece que la latencia de la ruta crítica es de solo 3 ciclos, con dos cadenas de 2 instrucciones, cada una de las cuales conduce al XOR. @Reinstate Monica: la respuesta de ζ-- se compila en una cadena descendente de 4 ciclos (para x86). El rendimiento del bucle de 5 ciclos se ve obstaculizado al incluir también un sub ingenuo en la ruta crítica, y el bucle genera un cuello de botella en la latencia.

Sin embargo, esto es inútil con clang. ¡Ni siquiera agrega y almacena en el mismo orden en que se cargó, por lo que ni siquiera está haciendo una buena canalización de software!

 # RISC-V clang (trunk) -O3 dec_mem_gnu(unsigned char*): lb a6, 7(a0) lb a7, 6(a0) lb t0, 5(a0) ... addi t1, a5, -1 addi t2, a1, -1 addi t3, a2, -1 ... sb a2, 7(a0) sb a1, 6(a0) sb a5, 5(a0) ... ret

No voy a tratar de encontrar el código, pero para una disminución de 1, puede disminuir el grupo de 8 1 y luego verificar para asegurarse de que los LSB de los resultados se hayan "volteado". Cualquier LSB que no haya cambiado indica que se produjo un acarreo de los 8 bits adyacentes. Debería ser posible elaborar una secuencia de AND/OR/XOR para manejar esto, sin bifurcaciones.