Đếm số 0 đứng đầu trong Int32

Question

Làm cách nào để đếm số 0 đứng đầu trong Int32? Vì vậy, những gì tôi muốn làm là viết một hàm trả về 30 nếu đầu vào của tôi Int32 là 2, vì ở dạng nhị phân Tôi có 0000000000000010.

Answer 1

Hãy lấy số 10 làm ví dụ. Nó có thể được ghi ở dạng nhị phân như sau:

00000000000000000000000000010100 

tiên chúng ta "bôi nhọ" bit quan trọng nhất trong các vị trí bit thấp hơn bằng cách chuyển phải và bitwise-ORing trên chính nó.

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

sau đó

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

Ở đây, bởi vì nó là một con số nhỏ, chúng tôi đã hoàn thành công việc, nhưng bằng cách lặp lại quá trình này cho đến một sự thay đổi quyền 16 bit, chúng ta có thể đảm bảo rằng đối với bất kỳ số bit 32 bit nào, chúng tôi đã đặt tất cả các bit từ 0 thành MSB của số gốc thành 1.

Bây giờ, nếu chúng ta đếm số 1 trong kết quả "bôi nhọ" của chúng tôi, chúng ta có thể trừ nó từ 32, và chúng ta còn lại với số lượng số 0 đứng đầu trong giá trị ban đầu.

Làm cách nào để đếm số lượng bit thiết lập trong một số nguyên? This page có thuật toán phép thuật để thực hiện điều đó ("thuật toán SWAR biến chính xác để thực hiện giảm cây" ... nếu bạn hiểu, bạn thông minh hơn tôi!), Dịch thành C# như sau:

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); 
} 

Bằng cách gạch chân phương pháp này bằng phương pháp "bôi nhọ" của chúng tôi ở trên, chúng tôi có thể tạo ra số 0 đầu tiên của số nguyên.

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

Trong 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)); 
} 

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

dịch vào C# được để lại như một bài tập nhỏ cho người đọc.

EDIT

Lý do tôi đã liên kết được, mà tôi không cần phải sao chép như sau (một lần nữa Trong 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

Số nguyên không có số không hàng đầu, cũng không làm họ hỗ trợ 32 chữ số. Điều đó đang được nói, bạn sẽ có thể tạo một hàm để làm điều này bằng cách chuyển đổi số nguyên thành chuỗi và kiểm tra độ dài:

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

Một số câu trả lời phức tạp xảy ra ở đây. Còn cái này thì sao?

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

Mặc dù bây giờ tôi đoán có thể có một số vấn đề với số âm và không có gì với loại giải pháp này.

Answer 6

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

Answer 7

Hãy thử điều này:

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

Come on guys, dừng lại hỏi "tại sao bạn muốn làm điều này hay điều đó". Trả lời nếu bạn có thể hoặc cứ tiếp tục. Việc đếm số 0 đứng đầu là một nhiệm vụ phổ biến trong nhiều vấn đề (ví dụ: thuật toán nén). Thậm chí còn có các hướng dẫn phần cứng x86 dành riêng cho điều đó (clz, bsr). Thật không may, bạn không thể sử dụng các hướng dẫn phần cứng đó trong C#, vì nội tại không được hỗ trợ (chưa). Chuyển đổi thành một chuỗi là một trò đùa tôi cho là vậy.

Biểu diễn nhị phân của int có các giới hạn được xác định rất rõ ràng. Trong thực tế, trong C# int chỉ là bí danh cho Int32. Như tên gọi của nó gợi ý, "Int32" luôn là số nguyên có dấu 32 bit, ngay cả khi bạn biên dịch dự án của bạn cho x64.

Và bạn không cần một số ma thuật voodo đặc biệt để tính toán số không hàng đầu: Đây là giải pháp toán học đơn giản mà làm việc:

Ở đây "x" là int của bạn (Int32):

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

Chỉnh sửa: Xin lỗi, tôi đã xem xét và sửa lại công thức của tôi. Do lỗi chính xác của phép tính số học kép, kết quả có thể không chính xác đối với một vài trường hợp biên. Vì vậy, nó vẫn cần một số "ma thuật voodo". Dòng thứ hai xử lý các trường hợp đó và tạo kết quả chính xác.

Answer 9

Bạn có thể nhận được hiệu suất tốt nhất sử dụng tính toán trước đếm

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

đếm số không hàng đầu/tìm tập đầu tiên/chút quét ngược lại là một điều phổ biến như vậy để muốn trong hệ điều hành và trình độ thấp lập trình khác hầu hết các phần cứng hỗ trợ CLZ theo hình thức của một hướng dẫn chu trình đơn. Và hầu hết các trình biên dịch c/C++ đều có trình biên dịch nội tại cho nó.

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

cũng nhất phần cứng và trình biên dịch cũng có số đuôi số không, số lượng pop/bit đếm hoạt động bit twiddling/đếm những, chẵn lẻ, bswap/lật endien, và một số quarky khác nhưng rất hữu ích.

Answer 11

Nhìn vào https://chessprogramming.wikispaces.com/BitScan để biết thông tin tốt về bitcanning.

Nếu bạn có thể kết hợp mã lắp ráp, hãy sử dụng các lệnh bộ xử lý LZCNT, TZCNT và POPCNT hiện đại.

Ngoài việc xem xét triển khai thực hiện Java cho Integer.

/** 
* 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

Nếu bạn muốn kết hợp mã lắp ráp để đạt hiệu suất cao nhất. Đây là cách bạn làm điều đó trong C#.

Đầu tiên mã hỗ trợ để làm cho nó có thể:

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)); 
} 

Sau đó, đây là lắp ráp để tạo ra các chức năng:

[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; 
}))(); 

Để tạo lắp ráp I started a ++ Dự án VC mới, tạo ra các chức năng tôi muốn, sau đó đi đến Debug -> Windows -> Tháo gỡ. Đối với các tùy chọn trình biên dịch, tôi vô hiệu hoá nội tuyến, bật nội tại, mã nhanh ưa thích, con trỏ khung bị bỏ qua, kiểm tra bảo mật bị vô hiệu hóa và kiểm tra SDL. Mã cho điều đó là:

#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; 
}