How to loop bit by bit over a long long in C++

Question

If I have long long x; in c++, how can I loop over each bit in the number to check if it zero or 1?

I would like to count the number of ones in the bits.

If it is just the count you want, there are faster methods. Discussion in http://stackoverflow.com/questions/109023/how-to-count-the-number-of-set-bits-in-a-32-bit-integer. Note that some of those methods require changes for long long. — DrC, Nov 18 '13 at 18:22

Raxvan · Answer 1 · 2016-12-10T10:45:53.880

16

You need to use shifting >> operator:

unsigned long long x = static_cast<unsigned long long>(your_value);
//unsigned long long fix for issue pointed out by @Zac Howland in comments
unsigned int count = 0;//number of 1 bits
while (x != 0)
{
    unsigned long long bit = x & 1;
    if( bit == 1 )
    {
        count ++;//...
    }
    else //zero
    {
        //...
    }
    x >>= 1;
}

There are other methods that do this in various ways, you can find them here (along with other stuff)

edited Dec 10 '16 at 10:45

answered Nov 18 '13 at 18:18

Raxvan

6,257
2
25
46

The one problem you may run into (implementation defined) is if `x` is negative. Some implementations implement a right-shift of a negative number by keeping the number negative, so you would never end up with `x == 0`. – Zac Howland Nov 18 '13 at 18:22
@Zac Howland that , i did not expect – Raxvan Nov 18 '13 at 18:23
There is no any need to do the shift operation. – Vlad from Moscow Nov 18 '13 at 18:27
@VladfromMoscow If all you are doing is counting bits, there is actually no need for the loop at all ... – Zac Howland Nov 18 '13 at 18:45
What if you need to count the largest number of consecutive bits set? This is useful in that case. – Mindaugas Bernatavičius Aug 27 '18 at 08:52

score 2 · Answer 2 · answered Nov 18 '13 at 18:24

2

You need not to do the shift operation.:)

size_t count = 0;

for ( long long v = x; v; v &= v - 1 ) ++count;

answered Nov 18 '13 at 18:24

Vlad from Moscow

301,070
26
186
335

You realize that `v &= v - 1` is basically a right-shift, right? :-P – Zac Howland Nov 18 '13 at 18:33
No it is not because left bits are not shifted and filled with zeoes. – Vlad from Moscow Nov 18 '13 at 18:41
Sure it is. What it buys you is a default shifting of 0's. That is, if you have `1111`, each iteration is basically the same as a `<< 1`. If you have `1001`, the first iteration is basically a `<< 3`. It is still effectively a right shift - just with a variable number of shifts determined by the positioning. For counting bits, you can get away without using a loop at all, though. – Zac Howland Nov 18 '13 at 18:43

Zac Howland · Answer 3 · 2013-11-18T18:26:13.107

0

const unsigned int BITCOUNT = sizeof(long long) * CHAR_BIT - 1;
// or
const unsigned int BITCOUNT = sizeof(unsigned long long) * CHAR_BIT;

for (unsigned int i = 0; i < BITCOUNT; ++i)
{
    unsigned int test_bit = 1LL << i;
    if (value & test_bit)
    {
        // do something
    }
}

If you just want the bit count, you can use the SWAR algorithm:

unsigned int bit_count(unsigned long long i)
{
    i = i - ((i >> 1) & 0x5555555555555555);
    i = (i & 0x3333333333333333) + ((i >> 2) & 0x3333333333333333);
    return (((i + (i >> 4)) & 0x0F0F0F0F0F0F0F0F) * 0x0101010101010101) >> 56;
}

edited Nov 18 '13 at 18:26

answered Nov 18 '13 at 18:20

Zac Howland

15,777
1
26
42

Why 8? :P (/pedantic - it should be `CHAR_BIT`) – Luchian Grigore Nov 18 '13 at 18:24

score 0 · Answer 4 · answered Nov 19 '20 at 14:06

The following program shows the process that is used to loop through a byte

#include <iostream>

int main()
{
    std::uint_fast8_t flags{ 0b10011000 };

    for (int i = 128; i >= 1; i /= 2)
    {
        if (flags & i)
            std::cout << '1';
        else
            std::cout << '0';
    }

    std::cout << '\n';
    return 0;
}

this prints: 10011000

How to loop bit by bit over a long long in C++

4 Answers4