9

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.

1
  • If it is just the count you want, there are faster methods. Discussion in stackoverflow.com/questions/109023/…. Note that some of those methods require changes for long long.
    – DrC
    Nov 18, 2013 at 18:22

4 Answers 4

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)

5
  • 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. Nov 18, 2013 at 18:22
  • @Zac Howland that , i did not expect
    – Raxvan
    Nov 18, 2013 at 18:23
  • There is no any need to do the shift operation. Nov 18, 2013 at 18:27
  • @VladfromMoscow If all you are doing is counting bits, there is actually no need for the loop at all ... Nov 18, 2013 at 18:45
  • What if you need to count the largest number of consecutive bits set? This is useful in that case. Aug 27, 2018 at 8:52
2

You need not to do the shift operation.:)

size_t count = 0;

for ( long long v = x; v; v &= v - 1 ) ++count;
3
  • You realize that v &= v - 1 is basically a right-shift, right? :-P Nov 18, 2013 at 18:33
  • No it is not because left bits are not shifted and filled with zeoes. Nov 18, 2013 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. Nov 18, 2013 at 18:43
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;
}
1
  • Why 8? :P (/pedantic - it should be CHAR_BIT) Nov 18, 2013 at 18:24
0

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.