Cách nhanh nhất để liệt kê thông qua bật bit của một số nguyên

Question

Cách nhanh nhất để liệt kê thông qua số nguyên và trả về số số mũ của mỗi bit được bật là gì? Đã xem ví dụ sử dụng < < và một ví dụ khác sử dụng Math.Pow. Tự hỏi liệu có điều gì khác thực sự nhanh hay không.

Cảm ơn.

Answer 1

Tôi tưởng tượng chuyển dịch bit sẽ là nhanh nhất. Untested, nhưng tôi nghĩ rằng sau đây nên được nhanh chóng (nhanh như IEnumerables được ít nhất).

IEnumerable<int> GetExponents(Int32 value) 
{ 
    for(int i=0; i<32; i++) 
    { 
     if(value & 1) 
      yield return i; 
     value >>= 1; 
    } 
} 

Nếu bạn muốn nó được nhanh hơn, bạn có thể xem xét việc trả lại một List<int> để thay thế.

Answer 2

Tôi đoán bit shifting (< <) là nhanh nhất.

Answer 3

Mảng dò tìm giá trị bit của một byte phải gần với tốc độ nhanh nhất bạn có thể thực hiện trong mã C# an toàn. Di chuyển mỗi 4 byte ra khỏi số nguyên (đúc thành uint nếu cần) và chỉ mục vào mảng.

Các phần tử của mảng tra cứu có thể là một mảng số mũ hoặc, tùy thuộc vào những gì bạn đang làm với các bit, có lẽ các đại biểu hoạt động.

Answer 4

Nhanh nhất cho những gì phân phối cho đầu vào? Nếu thông thường chỉ có một bit được thiết lập, thì điều này có thể nhanh hơn vòng lặp thông qua tìm kiếm các bit thiết lập.

Lấy từ câu trả lời được chấp nhận để tìm kiếm position of the least significant bit, lấy từ Bit Twiddling Hacks, giải pháp này lặp lại, tìm kiếm, xóa và trả lại vị trí của từng bit ít quan trọng nhất liên tiếp.

static int[] MulDeBruijnBitPos = new int[32] 
    { 
     0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
     31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
    }; 

    static IEnumerable<int> GetExponents(UInt32 v) 
    { 
     UInt32 m; 

     while(v != 0) { 
      m = (v & (UInt32) (-v)); 
      yield return MulDeBruijnBitPos[((UInt32) (m * 0x077CB531U)) >> 27]; 
      v ^= m; 
     } 
    } 

Nó chỉ lặp lại nhiều lần khi có bit được đặt.

Answer 5

nhanh nhất cách? Bảng tra cứu hầu như luôn là cách nhanh nhất. Tạo một mảng int [] [] với bốn tỷ mục, một cho mỗi int, chứa một mảng các số bạn muốn. Việc khởi tạo bảng sẽ mất một chút thời gian, tất nhiên nhưng việc tra cứu sẽ cực kỳ nhanh.

Tôi lưu ý rằng bạn chưa nói "nhanh nhất" có nghĩa là với độ chính xác đủ để mọi người thực sự trả lời câu hỏi. Nó có nghĩa là thời gian khấu hao nhanh nhất bao gồm thời gian khởi động, hoặc thời gian tra cứu cận biên giả định rằng chi phí khởi động có thể bị bỏ quên? Phác thảo giải pháp của tôi giả định sau này.

Rõ ràng một máy 32 bit với 2 tỷ byte không gian địa chỉ sẽ không có đủ không gian địa chỉ để lưu trữ ba mươi tỷ byte mảng. Tự tạo cho mình một máy 64 bit. Bạn sẽ cần ít nhất là nhiều bộ nhớ vật lý được cài đặt cũng như nếu bạn muốn nó được nhanh chóng - phân trang sẽ giết bạn nếu không.

Tôi chắc chắn hy vọng cặp nano giây bạn tiết kiệm được trên mỗi lần tra cứu sẽ đáng mua tất cả phần cứng bổ sung đó. Hoặc có thể bạn không thực sự là muốn cách nhanh nhất?

:-)

Answer 6

Chỉ để cho vui, đây là một lớp lót sử dụng LINQ.

Nó chắc chắn không phải là cách nhanh nhất để làm điều đó, mặc dù nó không xa phía sau các câu trả lời khác sử dụng yield và khối lặp.

int test = 42; 

// returns 1, 3, 5 
// 2^1 + 2^3 + 2^5 
// = 2 + 8 + 32 
// = 42 
var exponents = Enumerable.Range(0, 32).Where(x => ((test >> x) & 1) == 1); 

Để có giải pháp nhanh hơn, tôi có thể trả về bộ sưu tập đơn giản hơn là sử dụng khối lặp. Một cái gì đó như thế này:

int test = 2458217; 

// returns 0, 3, 5, 6, 9, 15, 16, 18, 21 
// 2^0 + 2^3 + 2^5 + 2^6 + 2^9 + 2^15 + 2^16 + 2^18 + 2^21 
// = 1 + 8 + 32 + 64 + 512 + 32768 + 65536 + 262144 + 2097152 
// = 2458217 
var exponents = GetExponents(test); 

// ... 

public static List<int> GetExponents(int source) 
{ 
    List<int> result = new List<int>(32); 

    for (int i = 0; i < 32; i++) 
    { 
     if (((source >> i) & 1) == 1) 
     { 
      result.Add(i); 
     } 
    } 

    return result; 
} 

Answer 7

IEnumerable sẽ không hoạt động. Tối ưu hóa của một số ví dụ trong chủ đề này:

một đầu tiên (nhanh nhất - 2,35 giây cho 10M chạy, phạm vi 1..10M):

static uint[] MulDeBruijnBitPos = new uint[32] 
{ 
    0, 1, 28, 2, 29, 14, 24, 3, 30, 22, 20, 15, 25, 17, 4, 8, 
    31, 27, 13, 23, 21, 19, 16, 7, 26, 12, 18, 6, 11, 5, 10, 9 
}; 

static uint[] GetExponents(uint value) 
{ 
    uint[] data = new uint[32]; 
    int enabledBitCounter = 0; 

    while (value != 0) 
    { 
     uint m = (value & (0 - value)); 
     value ^= m; 
     data[enabledBitCounter++] = MulDeBruijnBitPos[(m * (uint)0x077CB531U) >> 27]; 
    } 

    Array.Resize<uint>(ref data, enabledBitCounter); 
    return data; 
} 

phiên bản khác (nhanh thứ hai - 3 giây cho 10M chạy, phạm vi 1..10M):

static uint[] GetExponents(uint value) 
{ 
    uint[] data = new uint[32]; 
    int enabledBitCounter = 0; 

    for (uint i = 0; value > 0; ++i) 
    { 
     if ((value & 1) == 1) 
      data[enabledBitCounter++] = i; 
     value >>= 1; 
    } 

    Array.Resize<uint>(ref data, enabledBitCounter); 
    return data; 
} 

Answer 8

Nếu bạn sẽ không bị nghẹt thở trên một chút C++:

void func(int i, int& n, int a[]){ 
    n = 0; 
    if (i < 0) a[n++] = 31; 
    i <<= 1; 
    if (i < 0) a[n++] = 30; 
    i <<= 1; 
    if (i < 0) a[n++] = 29; 
    i <<= 1; 

    ... 

    if (i < 0) a[n++] = 0; 
}