Tìm bit SET thứ n trong một int

Question

Thay vì chỉ là bit đặt thấp nhất, tôi muốn tìm vị trí của bit thiết lập thấp nhất n. (Tôi KHÔNG nói về giá trị trên vị trí bit thứ n)

Ví dụ, nói tôi có:
0000 1101 1000 0100 1100 1000 1010 0000

Và tôi muốn tìm các bit thứ 4 được thiết lập. Sau đó, tôi muốn nó trở lại:
0000 0000 0000 0000 0100 0000 0000 0000

Nếu popcnt(v) < n, nó sẽ làm cho ý nghĩa nếu chức năng này trở 0, nhưng bất kỳ hành vi cho trường hợp này là chấp nhận được đối với tôi.

Tôi đang tìm kiếm thứ gì đó nhanh hơn vòng lặp nếu có thể.

Answer 1

Nó chỉ ra rằng nó thực sự có thể làm điều này mà không có vòng lặp. Nó là nhanh nhất để tính toán trước (ít nhất) 8 bit phiên bản của vấn đề này. Tất nhiên, các bảng này sử dụng dung lượng bộ nhớ cache, nhưng vẫn có một tốc độ thực trong hầu hết các kịch bản máy tính hiện đại. Trong mã này, n = 0 lợi nhuận chút ít thiết lập, n = 1 là thứ hai-to-nhất vv

Giải pháp với __popcnt

Có một giải pháp sử dụng các __popcnt nội tại (bạn cần __popcnt để đạt được tốc độ cực nhanh hoặc bất kỳ lợi ích tuyệt vời nào trên một giải pháp vòng lặp đơn giản sẽ được khắc phục. May mắn thay hầu hết các bộ xử lý thời đại SSE4 + đều hỗ trợ nó).

// lookup table for sub-problem: 8-bit v 
byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v < 256 and n < 8 

ulong nthSetBit(ulong v, ulong n) { 
    ulong p = __popcnt(v & 0xFFFF); 
    ulong shift = 0; 
    if (p <= n) { 
     v >>= 16; 
     shift += 16; 
     n -= p; 
    } 
    p = __popcnt(v & 0xFF); 
    if (p <= n) { 
     shift += 8; 
     v >>= 8; 
     n -= p; 
    } 

    if (n >= 8) return 0; // optional safety, in case n > # of set bits 
    return PRECOMP[v & 0xFF][n] << shift; 
} 

Điều này minh họa cách thức phân chia và cách tiếp cận chinh phục hoạt động.

chung Giải pháp

Ngoài ra còn có một giải pháp cho architectures- "chung" mà không __popcnt. Nó có thể được thực hiện bằng cách xử lý trong các khối 8 bit. Bạn cần một bảng tra cứu nhiều hơn cho bạn biết popcnt của một byte:

byte PRECOMP[256][8] = { .... } // PRECOMP[v][n] for v<256 and n < 8 
byte POPCNT[256] = { ... } // POPCNT[v] is the number of set bits in v. (v < 256) 

ulong nthSetBit(ulong v, ulong n) { 
    ulong p = POPCNT[v & 0xFF]; 
    ulong shift = 0; 
    if (p <= n) { 
     n -= p; 
     v >>= 8; 
     shift += 8; 
     p = POPCNT[v & 0xFF]; 
     if (p <= n) { 
      n -= p; 
      shift += 8; 
      v >>= 8; 
      p = POPCNT[v & 0xFF]; 
      if (p <= n) { 
       n -= p; 
       shift += 8; 
       v >>= 8; 
      } 
     } 
    } 

    if (n >= 8) return 0; // optional safety, in case n > # of set bits 
    return PRECOMP[v & 0xFF][n] << shift; 
} 

Điều này có thể, tất nhiên, được thực hiện với một vòng lặp, nhưng dưới hình thức trải ra nhanh hơn và các hình thức khác thường của vòng lặp sẽ làm cho nó không chắc rằng trình biên dịch có thể tự động hủy bỏ nó cho bạn.

Answer 2

Tôi không thể nhìn thấy một phương pháp mà không có vòng lặp, những gì lò xo để tâm trí sẽ được;

int set = 0; 
int pos = 0; 
while(set < n) { 
    if((bits & 0x01) == 1) set++; 
    bits = bits >> 1; 
    pos++; 
} 

sau đó, pos sẽ giữ vị trí thứ n thấp nhất có giá trị thiết lập bit.

Điều duy nhất mà tôi có thể nghĩ là phương pháp phân chia và chinh phục, có thể mang lại O (log (n)) thay vì O (n) ... nhưng có lẽ không.

Chỉnh sửa: bạn đã nói bất kỳ hành vi nào, vì vậy không chấm dứt là ok, phải không? : P

Answer 3

Bit Twiddling Hacks

chỉnh sửa: có không phải là một câu trả lời cụ thể cho vấn đề này, nhưng có tất cả các khối buildign cần thiết để giải quyết nó.

Answer 4

v-1 có số không ở đâu v có bit "một" ít quan trọng nhất, trong khi tất cả các bit quan trọng hơn đều giống nhau. Điều này dẫn đến các chức năng sau:

int ffsn(unsigned int v, int n) { 
    for (int i=0; i<n-1; i++) { 
     v &= v-1; // remove the least significant bit 
    } 
    return v & ~(v-1); // extract the least significant bit 
} 

Answer 5

def bitN (l: Long, i: Int) : Long = { 
    def bitI (l: Long, i: Int) : Long = 
    if (i == 0) 1L else 
    2 * { 
     if (l % 2 == 0) bitI (l/2, i) else bitI (l /2, i-1) 
    } 
    bitI (l, i)/2 
} 

Một phương pháp đệ quy (trong scala). Giảm dần i, vị trí, nếu một modulo2 là 1. Khi trở về, nhân với 2. Vì phép nhân được gọi là phép toán cuối cùng, nó không phải đệ quy đuôi, nhưng vì Longs có kích thước đã biết trước, nên stack tối đa cũng không phải là quá to.

scala> n.toBinaryString.replaceAll ("(.{8})", "$1 ") 
res117: java.lang.String = 10110011 11101110 01011110 01111110 00111101 11100101 11101011 011000 

scala> bitN (n, 40) .toBinaryString.replaceAll ("(.{8})", "$1 ") 
res118: java.lang.String = 10000000 00000000 00000000 00000000 00000000 00000000 00000000 000000 

Answer 6

Ngày nay việc này rất dễ dàng với PDEP từ số BMI2 instruction set. Đây là một phiên bản 64-bit với một số ví dụ:

#include <cassert> 
#include <cstdint> 
#include <x86intrin.h> 

inline uint64_t nthset(uint64_t x, unsigned n) { 
    return _pdep_u64(1ULL << n, x); 
} 

int main() { 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 0) == 
        0b0000'0000'0000'0000'0000'0000'0010'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 1) == 
        0b0000'0000'0000'0000'0000'0000'1000'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 3) == 
        0b0000'0000'0000'0000'0100'0000'0000'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 9) == 
        0b0000'1000'0000'0000'0000'0000'0000'0000); 
    assert(nthset(0b0000'1101'1000'0100'1100'1000'1010'0000, 10) == 
        0b0000'0000'0000'0000'0000'0000'0000'0000); 
} 

Answer 7

Dựa trên câu trả lời được đưa ra bởi Jukka Suomela, trong đó sử dụng một hướng dẫn cụ thể của máy mà có thể không nhất thiết phải có sẵn, nó cũng có thể viết một hàm thực hiện chính xác điều tương tự như _pdep_u64 mà không cần bất kỳ phụ thuộc máy nào. Nó phải lặp qua các bit thiết lập trong một trong các đối số, nhưng vẫn có thể được mô tả như là một hàm constexpr cho C++ 11.

constexpr inline uint64_t deposit_bits(uint64_t x, uint64_t mask, uint64_t b, uint64_t res) { 
    return mask != 0 ? deposit_bits(x, mask & (mask - 1), b << 1, ((x & b) ? (res | (mask & (-mask))) : res)) : res; 
} 

constexpr inline uint64_t nthset(uint64_t x, unsigned n) { 
    return deposit_bits(1ULL << n, x, 1, 0); 
}