Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Get an array of the bit positions within a 64-bit integer

OK, it may sound a bit complicated, but this is what I'm trying to do :

  • Take e.g. 10101010101
  • And return { 0, 2, 4, 6, 8, 10 } - an array with all of the positions of bits which are set

This is my code :

UINT DQBitboard::firstBit(U64 bitboard)
{
    static const int index64[64] = {
    63,  0, 58,  1, 59, 47, 53,  2,
    60, 39, 48, 27, 54, 33, 42,  3,
    61, 51, 37, 40, 49, 18, 28, 20,
    55, 30, 34, 11, 43, 14, 22,  4,
    62, 57, 46, 52, 38, 26, 32, 41,
    50, 36, 17, 19, 29, 10, 13, 21,
    56, 45, 25, 31, 35, 16,  9, 12,
    44, 24, 15,  8, 23,  7,  6,  5  };

    static const U64 debruijn64 = 0x07EDD5E59A4E28C2ULL;

    #pragma warning (disable: 4146)
    return index64[((bitboard & -bitboard) * debruijn64) >> 58];  
}

vector<UINT> DQBitboard::bits(U64 bitboard)
{
    vector<UINT> res;

    while (bitboard)
    {
        UINT first = DQBitboard::firstBit(bitboard);
        res.push_back(first);

        bitboard &= ~(1ULL<<first);
    }

    return res;
}

And the code surely does work.

My point is :

  • Is there any faster implementation you have in mind?
  • Do you notice anything that could be optimized? If so, what?

Hints :

  • UINT is a typedef of unsigned int
  • U64 is a typedef of unsigned long long
  • Both methods are static inline.
like image 255
Dr.Kameleon Avatar asked Dec 29 '12 23:12

Dr.Kameleon


People also ask

How can I use 64-bit int in C++?

Microsoft C/C++ features support for sized integer types. You can declare 8-, 16-, 32-, or 64-bit integer variables by using the __intN type specifier, where N is 8, 16, 32, or 64.

Can Python handle 64-bit integers?

Based on the integer types, you can determine the ranges of the integers those types can represent. Python, however, doesn't use a fixed number of bit to store integers. Instead, Python uses a variable number of bits to store integers. For example, 8 bits, 16 bits, 32 bits, 64 bits, 128 bits, and so on.

How much can a 64-bit integer hold?

A 64-bit signed integer. It has a minimum value of -9,223,372,036,854,775,808 and a maximum value of 9,223,372,036,854,775,807 (inclusive). A 64-bit unsigned integer.

Can you execute Bit Array in C language?

This is a C Program to implement Bit Array. A bit array is an array data structure that compactly stores bits. It can be used to implement a simple set data structure. A bit array is effective at exploiting bit-level parallelism in hardware to perform operations quickly.


1 Answers

Here is another suggestion that can be profiled (can be combined with other suggestions for further optimization). Note, the loop here is O(number of set bits).

vector<UINT> bits_set (UINT64 data) 
{
    UINT n;
    vector<UINT> res;
    res.reserve(64);
    for (n = 0; data != 0; n++, data &= (data - 1))
    {
        res.push_back(log2(data & ~(data-1)));
    }
    return res;
}
like image 139
SomeWittyUsername Avatar answered Sep 17 '22 18:09

SomeWittyUsername