Cuente ceros a la izquierda en un Int32

Question

¿Cómo cuento los ceros a la izquierda en un Int32? Así que lo que quiero hacer es escribir una función que devuelve 30 si mi entrada Int32 es 2, ya que en binario tengo 0000000000000010.

Answer 1

Tomemos el número 10 como ejemplo. Se puede afirmar en binario de la siguiente manera:

00000000000000000000000000010100 

En primer lugar, "mancha" el bit más significativo sobre las posiciones de bits más bajas por la derecha y el cambio a nivel de bits operación OR sobre sí misma.

00000000000000000000000000010100 
or 00000000000000000000000000001010 (right-shifted by 1) 
is 00000000000000000000000000011100 

continuación

00000000000000000000000000011100 
or 00000000000000000000000000000111 (right-shifted by 2) 
is 00000000000000000000000000011111 

aquí, porque es un número pequeño, que ya ha completado el trabajo, pero repitiendo el proceso hasta un desplazamiento a la derecha de 16 bits, podemos asegurar que para cualquier número de 32 bits, hemos establecido todos los bits de 0 en el MSB del número original en 1.

Ahora, si contamos el número de 1s en nuestro resultado "manchado", podemos simplemente restar es de 32, y nos queda el número de ceros a la izquierda en el valor original.

¿Cómo se cuenta el número de bits configurados en un número entero? This page tiene un algoritmo mágico para hacer justamente eso ("un algoritmo SWAR de precisión variable para realizar una reducción de árbol" ... si lo obtiene, ¡usted es más listo que yo!), Que se traduce en C# como sigue:

int PopulationCount(int x) 
{ 
    x -= ((x >> 1) & 0x55555555); 
    x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); 
    x = (((x >> 4) + x) & 0x0f0f0f0f); 
    x += (x >> 8); 
    x += (x >> 16); 
    return (x & 0x0000003f); 
} 

por inlining este método con nuestro método de "manchas" por encima, podemos producir un método muy rápido, libre de bucles y condicionales-libre para contar los ceros a la izquierda de un número entero.

int LeadingZeros(int x) 
{ 
    const int numIntBits = sizeof(int) * 8; //compile time constant 
    //do the smearing 
    x |= x >> 1; 
    x |= x >> 2; 
    x |= x >> 4; 
    x |= x >> 8; 
    x |= x >> 16; 
    //count the ones 
    x -= x >> 1 & 0x55555555; 
    x = (x >> 2 & 0x33333333) + (x & 0x33333333); 
    x = (x >> 4) + x & 0x0f0f0f0f; 
    x += x >> 8; 
    x += x >> 16; 
    return numIntBits - (x & 0x0000003f); //subtract # of 1s from 32 
} 

Answer 2

En C:

unsigned int 
lzc(register unsigned int x) 
{ 
     x |= (x >> 1); 
     x |= (x >> 2); 
     x |= (x >> 4); 
     x |= (x >> 8); 
     x |= (x >> 16); 
     return(WORDBITS - ones(x)); 
} 

(desde http://aggregate.org/MAGIC/#Leading Zero Count)

Traducción en C# se deja como un ejercicio trivial para el lector.

EDITAR

La razón que dio el enlace estaba, que no necesito copiar los siguientes (de nuevo en C):

#define WORDBITS 32 

unsigned int 
ones(unsigned int x) 
{ 
     /* 32-bit recursive reduction using SWAR... 
     but first step is mapping 2-bit values 
     into sum of 2 1-bit values in sneaky way 
    */ 
     x -= ((x >> 1) & 0x55555555); 
     x = (((x >> 2) & 0x33333333) + (x & 0x33333333)); 
     x = (((x >> 4) + x) & 0x0f0f0f0f); 
     x += (x >> 8); 
     x += (x >> 16); 
     return(x & 0x0000003f); 
} 

Answer 3

enteros no tienen ceros a la izquierda, ni tampoco soporta 32 dígitos. Dicho esto, usted debe ser capaz de crear una función para hacer esto mediante la conversión del número entero a una cadena, y la comprobación de la longitud:

private int GetIntegerOffsetLength(int value) 
{ 
    //change 32 to whatever your upper bound is 
    return (32 - (value.ToString().Length + 1)); 
} 

Answer 4

private int GetIntegerOffsetLength(int value) 
{ 
    return (32 - (Convert.ToString(value, 2).Length); 
} 

Answer 5

Algunas respuestas complicadas pasando aquí. ¿Qué tal esto?

private int LeadingZeroes(int value) 
{ 
    return (32 - (Convert.ToString(value, 2).Length)); 
} 

Aunque ahora supongo que puede haber algunos problemas con números negativos y otras cosas con este tipo de solución.

Answer 6

32 - Convert.ToString(2,2).Count() 

Answer 7

Prueba esto:

static int LeadingZeros(int value) 
{ 
    // Shift right unsigned to work with both positive and negative values 
    var uValue = (uint) value; 
    int leadingZeros = 0; 
    while(uValue != 0) 
    { 
     uValue = uValue >> 1; 
     leadingZeros++; 
    } 

    return (32 - leadingZeros); 
} 

Answer 8

Vamos chicos, dejar de preguntar "¿por qué quiere hacer esto o aquello". Responda si puede o simplemente continúe. El conteo de ceros a la izquierda es una tarea común en muchos problemas (por ejemplo, algoritmos de compresión). Incluso hay instrucciones de hardware x86 dedicadas a eso (clz, bsr). Desafortunadamente, no puede usar esas instrucciones de hardware en C#, porque los intrínsecos no son compatibles (todavía). Conversión en una cadena era una broma, supongo.

La representación binaria de int tiene límites muy bien definidos. De hecho, en C# int es solo un alias para Int32. Como sugiere su namge, "Int32" siempre es un entero con signo de 32 bits, incluso si compila su proyecto para x64.

Y usted no necesita un poco de magia especial voodo para calcular los ceros iniciales: Aquí es una solución matemática simple que funciona:

aquí "X" es su int (Int32):

int LeadingZeros = (int)(32 - Math.Log((double)x + 1, 2d)); 
LeadingZeros += (int)((x - (0x80000000u >> LeadingZeros)) >> 31); 

Edición: Lo siento, revisé y corrigí mi fórmula. Debido a los errores de precisión de la aritmética doble, el resultado puede ser incorrecto para pocos casos límite. Por lo tanto, todavía necesita un poco de "magia vudú". La segunda línea maneja esos casos y produce el resultado correcto.

Answer 9

Usted puede consiguió un mejor rendimiento utilizando recuentos precalculados

public static class BitCounter 
{ 
    private static readonly int[] _precomputed = new[] 
     { 
      0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
      1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
      2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
      3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
      4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 
     }; 

    public static int CountOn(int value) 
    { 
     return _precomputed[value >> 24] + 
       _precomputed[(value << 8) >> 24] + 
       _precomputed[(value << 16) >> 24] + 
       _precomputed[value & 0xFF]; 
    } 

    public static int CountOff(int value) 
    { 
     return 32 - CountOn(value); 
    } 
} 

Answer 10

recuento de ceros a la izquierda/find primer set/bit exploración inversa es una cosa normal que desee en el sistema operativo y otra programación de bajo nivel de la mayoría del hardware soporta clz en forma de una instrucción de ciclo único. Y la mayoría de los compiladores c/C++ tienen un compilador intrínseco.

http://en.wikipedia.org/wiki/Find_first_set

también la mayoría del hardware y los compiladores también tienen cuenta de ceros, el recuento de pop/bit de recuento/recuento queridos, paridad, bswap/flip endien, y varios otros Quarky pero muy útiles operaciones de bits haciendo girar.

Answer 11

Mire https://chessprogramming.wikispaces.com/BitScan para obtener buena información sobre bitscanning.

Si puede mezclar el código ensamblador, utilice los modernos comandos del procesador LZCNT, TZCNT y POPCNT.

Aparte de eso, eche un vistazo a la implementación de Java para Entero.

/** 
* Returns the number of zero bits preceding the highest-order 
* ("leftmost") one-bit in the two's complement binary representation 
* of the specified {@code int} value. Returns 32 if the 
* specified value has no one-bits in its two's complement representation, 
* in other words if it is equal to zero. 
* 
* <p>Note that this method is closely related to the logarithm base 2. 
* For all positive {@code int} values x: 
* <ul> 
* <li>floor(log<sub>2</sub>(x)) = {@code 31 - numberOfLeadingZeros(x)} 
* <li>ceil(log<sub>2</sub>(x)) = {@code 32 - numberOfLeadingZeros(x - 1)} 
* </ul> 
* 
* @param i the value whose number of leading zeros is to be computed 
* @return the number of zero bits preceding the highest-order 
*  ("leftmost") one-bit in the two's complement binary representation 
*  of the specified {@code int} value, or 32 if the value 
*  is equal to zero. 
* @since 1.5 
*/ 
public static int numberOfLeadingZeros(int i) { 
    // HD, Figure 5-6 
    if (i == 0) 
     return 32; 
    int n = 1; 
    if (i >>> 16 == 0) { n += 16; i <<= 16; } 
    if (i >>> 24 == 0) { n += 8; i <<= 8; } 
    if (i >>> 28 == 0) { n += 4; i <<= 4; } 
    if (i >>> 30 == 0) { n += 2; i <<= 2; } 
    n -= i >>> 31; 
    return n; 
} 

Answer 12

Si desea mezclar el código de ensamblaje para obtener un rendimiento máximo. Así es como haces eso en C#.

En primer lugar el código de soporte para que sea posible:

using System.Runtime.InteropServices; 
using System.Runtime.CompilerServices; 
using static System.Runtime.CompilerServices.MethodImplOptions; 

/// <summary> Gets the position of the right most non-zero bit in a UInt32. </summary> 
[MethodImpl(AggressiveInlining)] public static int BitScanForward(UInt32 mask) => _BitScanForward32(mask); 

/// <summary> Gets the position of the left most non-zero bit in a UInt32. </summary> 
[MethodImpl(AggressiveInlining)] public static int BitScanReverse(UInt32 mask) => _BitScanReverse32(mask); 


[DllImport("kernel32.dll", SetLastError = true)] 
private static extern IntPtr VirtualAlloc(IntPtr lpAddress, uint dwSize, uint flAllocationType, uint flProtect); 

private static TDelegate GenerateX86Function<TDelegate>(byte[] x86AssemblyBytes) { 
    const uint PAGE_EXECUTE_READWRITE = 0x40; 
    const uint ALLOCATIONTYPE_MEM_COMMIT = 0x1000; 
    const uint ALLOCATIONTYPE_RESERVE = 0x2000; 
    const uint ALLOCATIONTYPE = ALLOCATIONTYPE_MEM_COMMIT | ALLOCATIONTYPE_RESERVE; 
    IntPtr buf = VirtualAlloc(IntPtr.Zero, (uint)x86AssemblyBytes.Length, ALLOCATIONTYPE, PAGE_EXECUTE_READWRITE); 
    Marshal.Copy(x86AssemblyBytes, 0, buf, x86AssemblyBytes.Length); 
    return (TDelegate)(object)Marshal.GetDelegateForFunctionPointer(buf, typeof(TDelegate)); 
} 

Entonces aquí está el conjunto para generar las funciones:

[UnmanagedFunctionPointer(CallingConvention.Cdecl)] 
private delegate Int32 BitScan32Delegate(UInt32 inValue); 

private static BitScan32Delegate _BitScanForward32 = (new Func<BitScan32Delegate>(() => { //IIFE 
    BitScan32Delegate del = null; 
    if(IntPtr.Size == 4){ 
     del = GenerateX86Function<BitScan32Delegate>(
     x86AssemblyBytes: new byte[20] { 
     //10: int32_t BitScanForward(uint32_t inValue) { 
      0x51,          //51     push  ecx 
      //11: unsigned long i; 
      //12: return _BitScanForward(&i, inValue) ? i : -1; 
      0x0F, 0xBC, 0x44, 0x24, 0x08,    //0F BC 44 24 08  bsf   eax,dword ptr [esp+8] 
      0x89, 0x04, 0x24,       //89 04 24    mov   dword ptr [esp],eax 
      0xB8, 0xFF, 0xFF, 0xFF, 0xFF,    //B8 FF FF FF FF  mov   eax,-1    
      0x0F, 0x45, 0x04, 0x24,      //0F 45 04 24   cmovne  eax,dword ptr [esp] 
      0x59,          //59     pop   ecx 
      //13: } 
      0xC3,          //C3     ret 
     }); 
    } else if(IntPtr.Size == 8){ 
     del = GenerateX86Function<BitScan32Delegate>( 
     //This code also will work for UInt64 bitscan. 
     // But I have it limited to UInt32 via the delegate because UInt64 bitscan would fail in a 32bit dotnet process. 
      x86AssemblyBytes: new byte[13] { 
      //15: unsigned long i; 
      //16: return _BitScanForward64(&i, inValue) ? i : -1; 
      0x48, 0x0F, 0xBC, 0xD1,   //48 0F BC D1   bsf   rdx,rcx 
      0xB8, 0xFF, 0xFF, 0xFF, 0xFF,  //B8 FF FF FF FF  mov   eax,-1 
      0x0F, 0x45, 0xC2,     //0F 45 C2    cmovne  eax,edx 
      //17: } 
      0xC3        //C3     ret 
     }); 
    } 
    return del; 
}))(); 


private static BitScan32Delegate _BitScanReverse32 = (new Func<BitScan32Delegate>(() => { //IIFE 
    BitScan32Delegate del = null; 
    if(IntPtr.Size == 4){ 
     del = GenerateX86Function<BitScan32Delegate>(
     x86AssemblyBytes: new byte[20] { 
      //18: int BitScanReverse(unsigned int inValue) { 
      0x51,          //51     push  ecx 
      //19: unsigned long i; 
      //20: return _BitScanReverse(&i, inValue) ? i : -1; 
      0x0F, 0xBD, 0x44, 0x24, 0x08,    //0F BD 44 24 08  bsr   eax,dword ptr [esp+8] 
      0x89, 0x04, 0x24,       //89 04 24    mov   dword ptr [esp],eax 
      0xB8, 0xFF, 0xFF, 0xFF, 0xFF,    //B8 FF FF FF FF  mov   eax,-1 
      0x0F, 0x45, 0x04, 0x24,      //0F 45 04 24   cmovne  eax,dword ptr [esp] 
      0x59,          //59     pop   ecx 
      //21: } 
      0xC3,          //C3     ret 
     }); 
    } else if(IntPtr.Size == 8){ 
     del = GenerateX86Function<BitScan32Delegate>( 
     //This code also will work for UInt64 bitscan. 
     // But I have it limited to UInt32 via the delegate because UInt64 bitscan would fail in a 32bit dotnet process. 
      x86AssemblyBytes: new byte[13] { 
      //23: unsigned long i; 
      //24: return _BitScanReverse64(&i, inValue) ? i : -1; 
      0x48, 0x0F, 0xBD, 0xD1,   //48 0F BD D1   bsr   rdx,rcx 
      0xB8, 0xFF, 0xFF, 0xFF, 0xFF,  //B8 FF FF FF FF  mov   eax,-1 
      0x0F, 0x45, 0xC2,     //0F 45 C2    cmovne  eax,edx 
      //25: } 
      0xC3        //C3     ret 
     }); 
    } 
    return del; 
}))(); 

Con el fin de generar el conjunto de E inició un nuevo proyecto de VC++, creado las funciones que quería, luego fui a Depurar -> Windows -> Desensamblar. Para las opciones del compilador, desactivé la alineación, las características intrínsecas habilitadas, el código rápido preferido, los punteros de marco omitidos, las comprobaciones de seguridad desactivadas y las comprobaciones de SDL. El código para eso es:

#include "stdafx.h" 
#include <intrin.h> 

#pragma intrinsic(_BitScanForward) 
#pragma intrinsic(_BitScanReverse) 
#pragma intrinsic(_BitScanForward64) 
#pragma intrinsic(_BitScanReverse64) 


__declspec(noinline) int _cdecl BitScanForward(unsigned int inValue) { 
    unsigned long i; 
    return _BitScanForward(&i, inValue) ? i : -1; 
} 
__declspec(noinline) int _cdecl BitScanForward64(unsigned long long inValue) { 
    unsigned long i; 
    return _BitScanForward64(&i, inValue) ? i : -1; 
} 
__declspec(noinline) int _cdecl BitScanReverse(unsigned int inValue) { 
    unsigned long i; 
    return _BitScanReverse(&i, inValue) ? i : -1; 
} 
__declspec(noinline) int _cdecl BitScanReverse64(unsigned long long inValue) { 
    unsigned long i; 
    return _BitScanReverse64(&i, inValue) ? i : -1; 
}