Fastest way to find the value of a specific bit in a number in C++

zucculent 0
Viewed 91

I'm trying to write a program where I use the last 25 bits of a 32-bit integer to represent a 5x5 bingo board. I'm going to be looking at specific places a lot. What's the most time-efficient way to find the value of a given bit?

My guess is either:

int findBit (int a, int place){
    return a & (1 << place);
}

or

int findBit (int a, int place){
    return a / (1 << place) % 2;
}

or perhaps there is some built-in function that C++ has?

bit integer c++
2 Answers

Bitwise operations are prolific and efficient.

I crafted a test file using bitwise (the - below) and your modular division method (+ below). The difference in assembly is shown in a diff below:

-   and w8, w8, w9
+   sdiv    w8, w8, w9
+   mov w10, #2
+   sdiv    w9, w8, w10
+   mul w9, w9, w10
+   subs    w8, w8, w9

In the test, I performed the operations one trillion two hundred eighty billion times. Here are the times with x1 being bitwise and x2 being modular division:

% time ./x1 ; time ./x2
18328383850248350848
5.174u 0.031s 0:05.31 97.9% 0+0k 0+0io 0pf+0w
12690158593672146048
6.440u 0.037s 0:06.53 99.0% 0+0k 0+0io 0pf+0w

I ran this test many times, and found the results are similar. The bitwise is about 1 1/2 second faster.

Do you need to worry about the performance of this operation on modern computers?
No.

Hasty Benchmark - not scientific 

int main() {
    int a = INT_MAX/16, i;
    unsigned long b;
    for (; a > 0; a--) {
        for (i = 0; i < 32; i++) {
            b += a & (1 << i);
        }
    }
    printf("%lu\n", b);
}
James Risner0

It is likely that a good optimizer will substitute a / (1 << place) % 2 with (a >> place) & 1, but if not, the cost of a division and a modulo are terrible. The latter relation should be as efficient as a & (1 << place).

You can possibly do even better by directly passing the value 1 << place instead of place, assuming that the calling function can work with it. Anyway it is likely that such a nano optimization would have no measurable effect.

Yves Daoust0
Related