Chỉ số bit đặt hàng thấp nhất

Question

Tôi muốn tìm cách nhanh nhất để lấy chỉ mục của bit đặt hàng thấp nhất trong một thời gian dài. tức là:

00101001001000 -> 3 

Các giải pháp liên quan đến chuyển mạch và dịch chuyển quá chậm. ví dụ:

int i; 
if(bits == 0ULL) { 
    i = 64; 
} else { 
    for(i = 0;!(bits & 1ULL);i++) 
    bits >>= 1; 
} 

EDIT: Thông tin về việc sử dụng

Chức năng sử dụng ffsll có thể không thực sự làm giảm việc sử dụng của nó, nhưng ở đây nó được (đơn giản hóa tất nhiên). Nó chỉ lặp lại thông qua các chỉ mục và làm điều gì đó với chúng. Chức năng này có lẽ là chức năng được sử dụng rộng rãi nhất trong toàn bộ ứng dụng của tôi mặc dù có rất nhiều bộ nhớ đệm về giá trị của nó. Đó là máy phát điện di chuyển hợp pháp trong công cụ tìm kiếm alpha-beta của tôi.

while(bits){ 
    index = ffsll(bits); 
    doSomething(index); 
    index &= index-1; 
} 

Answer 1

Intel có hướng dẫn chuyên biệt để tìm bit đặt hàng thấp nhất hoặc cao nhất. BSF có vẻ như những gì bạn cần. khi thực hiện nó ở đồng bằng C, có thể bit twiddling hacks page có những gì bạn cần.

Ít nhất bạn cũng có thể sử dụng bảng nibbles hoặc byte để tăng tốc mọi thứ. Một cái gì đó như thế này (chứng minh cho int, nhưng dễ dàng thay đổi để longlong khi cần thiết).

/* 
0000 - 0 
0001 - 1 
0010 - 2 
0011 - 1 
0100 - 3 
0101 - 1 
0110 - 2 
0111 - 1 
1000 - 4 
1001 - 1 
1010 - 2 
1011 - 1 
1100 - 3 
1101 - 1 
1110 - 2 
1111 - 1 
*/ 

int ffs(int i) { 
    int ret = 0; 
    int j = 0; 
    static const int _ffs_tab[] = 
     { 0, 1, 2, 1, 3, 1, 2, 1, 4, 1, 2, 1, 3, 1, 2, 1 }; 

    while((i != 0) && (ret == 0)) { 
     ret = _ffs_tab[i & 0x0f]; 

     if(ret > 0) { 
      break; 
     } 

     i >>= 4; 
     j += 4; 

     /* technically the sign bit could stay, so we mask it out to be sure */ 
     i &= INT_MAX; 
    } 

    if(ret != 0) { 
     ret += j; 
    } 

    return ret; 
} 

Answer 2

Nhanh nhất tôi tìm thấy là ffsll(long long) trong chuỗi.h.

Answer 3

Làm cách nào để triển khai loại tìm kiếm nhị phân?

Nhìn vào các bit thấp có được từ một chút khôn ngoan và giá trị mặt nạ là tất cả những giá trị trong nửa thấp. Nếu giá trị đó bằng 0, bạn biết bit nhỏ nhất nằm ở nửa trên của số.

người khác cắt giảm điều này một nửa và quay lại.

Answer 4

Làm thế nào về một cái gì đó như thế này? Nó làm giảm số lượng vòng lặp đáng kể.

int shifts = 0; 
if ((bits & 0xFFFFFFFFFFFFULL) == 0) // not in bottom 48 bits 
{ 
    shifts = 48; 
} 
else if ((bits & 0xFFFFFFFFFFULL == 0) // not in bottom 40 bits 
{ 
    shifts = 40; 
} 
else 
// etc 

bits >>= shifts; // do all the shifts at once 

// this will loop at most 8 times 
for(i = 0;!(bits & 1ULL);i++) 
    bits >>= 1; 

index = shifts + i; 

Answer 5

Bạn có thể cách ly bit được đặt thấp nhất với x & (~x + 1); điều này mang lại cho bạn giá trị bit thấp nhất, không phải chỉ mục (ví dụ: nếu x = 01101000, thì kết quả là 00001000). Cách nhanh nhất mà tôi biết để nhận được từ đó đến chỉ mục có thể là một tuyên bố chuyển đổi:

switch(x & (~x + 1)) 
{ 
    case  0ULL: index = -1; break; 
    case  1ULL: index = 0; break; 
    case  2ULL: index = 1; break; 
    case  4ULL: index = 2; break; 
    ... 
    case 9223372036854775808ULL: index = 63; break; 
} 

Xấu xí, nhưng không liên quan đến vòng lặp.

Answer 6

Tôi đã viết hai hàm, chúng trả về kết quả tương tự như ffsll().

int func1(uint64_t n){ 
    if(n == 0) return 0; 
    n ^= n-1; 
    int i = 0; 
    if(n >= 1ull<<32){ n>>=32; i+=32; } 
    if(n >= 1ull<<16){ n>>=16; i+=16; } 
    if(n >= 1ull<< 8){ n>>= 8; i+= 8; } 
    if(n >= 1ull<< 4){ n>>= 4; i+= 4; } 
    if(n >= 1ull<< 2){ n>>= 2; i+= 2; } 
    if(n >= 1ull<< 1){   i+= 1; } 
    return i+1; 
} 

int func2(uint64_t n){ 
    return n? ((union ieee754_float)((float)(n^(n-1)))).ieee.exponent-126: 0; 
} 

Tôi không biết nhanh nhất: ffsll(), func1() hoặc func2()?

Answer 7

bạn có thể giảm một nửa độ phức tạp của thuật toán kiểm tra trước nếu số của bạn là số lẻ hoặc thậm chí. Nếu nó thậm chí bạn có bit thứ tự thấp nhất là bit đầu tiên.

Đối với các trường hợp lạ bạn có thể thực hiện tìm kiếm nhị phân như vậy ...

Answer 8

Điều này có thể hoạt động với 32 bit. Nên đủ dễ dàng để mở rộng đến 64.

// all bits left of lsb become 1, lsb & right become 0 
y = x^(-x); 

// XOR a shifted copy recovers a single 1 in the lsb's location 
u = y^(y >> 1); 

// .. and isolate the bit in log2 of number of bits 
i0 = (u & 0xAAAAAAAA) ? 1 : 0; 
i1 = (u & 0xCCCCCCCC) ? 2 : 0; 
i2 = (u & 0xF0F0F0F0) ? 4 : 0; 
i3 = (u & 0xFF00FF00) ? 8 : 0; 
i4 = (u & 0xFFFF0000) ? 16 : 0; 
index = i4 | i3 | i2 | i1 | i0; 

Rõ ràng, nếu có cách nào đó để phần cứng thực hiện điều đó, tức là nếu có sẵn hướng dẫn CPU đặc biệt, đó là cách để thực hiện.

Answer 9

Nếu sử dụng Visual Studio, _BitScanForward:

• http://msdn.microsoft.com/en-us/library/wfd9z0bb(VS.80).aspx (_BitScanForward)

Đối với gcc, hãy thử __builtin_ctz hoặc __builtin_ffs:

• http://developer.apple.com/mac/library/documentation/DeveloperTools/gcc-4.0.1/gcc/Other-Builtins.html (random gcc intrinsics documentation)

Như mọi khi, mã được tạo nên được tư vấn để đảm bảo các hướng dẫn chính xác được tạo ra.

Answer 10

Dưới đây là hai hiện thực, trước hết bởi intrinsics/lắp ráp, thứ hai là bởi c/C++ (Index bắt đầu từ 0)

unsigned int bsf_asm(unsigned int b) 
{ 

    // b == 0 is undefined 

#if defined(\__GNUC__) 

    return __builtin_ctz(b); 

#else 

    __asm bsf eax, b; 

#endif 

} 


unsigned int bsf(unsigned int b) 
{ 

    // b == 0 is undefined 

    static const unsigned char btal[] = {0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0}; 

    int i = 0; 
    if(!(b & 0x0000ffff)) 
    { 
     b>>=16; 
     i+=16; 
    } 

    if(!(b & 0x000000ff)) 
    { 
     b>>=8; 
     i+=8; 
    } 

    if(!(b & 0x0000000f)) 
    { 
     b>>=4; 
     i+=4; 
    } 

    return i+btal[b&0x0f]; 

} 

Answer 11

Để có được quyền nhất thiết bit biểu thức sau đây có thể được sử dụng

Hãy xem xét các biến như x

x & ~ (x - 1) đưa ra một số nhị phân mà chỉ chứa các bit thiết lập với phần còn lại tất cả zero

Ví dụ

x  = 0101 
x-1 = 0100 
~(x-1) = 1011 

x & ~ (x - 1) = 0100 

Bây giờ liên tục thay đổi số nhị phân này sang phải cho đến khi số không và đếm số ca làm cho số bit được đặt đúng nhất.