Thread: Understanding this bitwise function

  1. #1
    Registered User
    Join Date
    Nov 2013
    Posts
    107

    Understanding this bitwise function

    How does this bitwise function work(below), if you are ANDing two 8-bit numbers I understand that but as ints are either two or four bytes do you just set all the bits out in a row, For example to AND two 8-bit bytes you would do

    00000001
    00000011
    -------- ANDing would give
    00000001

    So how do you AND an int?

    Is it just,

    01010101010101010101010101010101
    10101010101010101010101010101010

    etc...

    This function also creates negative values for the (x-1) part and -1 for an unsigned int is 4294967295

    Code:
    int count_ones(unsigned int x)
    {
        int result = 0;
    
        while(x != 0) {
            result++;
            x = x & (x-1);
            cout << x << "\n";
        }
    
        return result;
    }
    So how exactly would you explain this on paper?

  2. #2
    Registered User
    Join Date
    Apr 2013
    Posts
    1,654
    x = x & (x-1) is used to clear the least significant bit that is set in x. As the function states, it's counting the number of one bits.

    Note there's an intrinsic function, popcnt, that uses a single X86 instruction to count the number of 1 bits, if it's available on your processor

  3. #3
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    Quote Originally Posted by jim_0 View Post
    How does this bitwise function work(below), if you are ANDing two 8-bit numbers I understand that but as ints are either two or four bytes do you just set all the bits out in a row, For example to AND two 8-bit bytes you would do
    Yes -- it's the same, just longer numbers. You can do bitwise stuff to anything that's got bits -- strings, floating point, anything. Though the compiler will try pretty hard to stop you in some of those cases, but hey, that's what pointers are for.


    Is it just,

    01010101010101010101010101010101
    10101010101010101010101010101010
    etc...
    Exactly.

    This function also creates negative values for the (x-1) part and -1 for an unsigned int is 4294967295

    Code:
    int count_ones(unsigned int x)
    {
        int result = 0;
    
        while(x != 0) {
            result++;
            x = x & (x-1);
            cout << x << "\n";
        }
    
        return result;
    }
    So how exactly would you explain this on paper?
    I don't follow what you mean about negative numbers. Signed integer over/overflow is undefined by the C standard, if I recall my facts correctly, so it'd be a very bad idea to use it.
    Unsigned -- yes, 0-1 will give 0xffffffff. That can't happen in this function though because of the while loop check for 0.

    As for how it works, I do get it but I don't think I can explain without a pile of binary. So let's do that.....

    Take 290, which is 100100010. Because that isn't 0, straight away we know there are some ones to count.
    x-1 is 100100001. The & doesn't make any difference yet
    x-1 again is 288, 100100000

    So far have been ticking off the 1s quite nicely. Next x-1 is 287, which is 100011111. Putting it next to the release result:

    288 100100000
    287 100011111

    The subtraction has meant several more bits get set. We're not interested in these, so we use the previous value as a mask to get rid of the unwanted bits.
    That gives 256: 100000000

    255: 011111111'
    Those two mask each other out, leaving 0.

    There were 3 ones set initially, and every subtraction removes a 1. Either directly if it's the bottom bit, or indrectly by causing a carry to set lots of ones that are then cleared. Because of the &, no bit that has been cleared can become set again, so the number of bit clearing iterations gives the number of set bits.

    I don't think I could explain it on 'paper' like proper paper.

  4. #4
    Registered User
    Join Date
    Apr 2013
    Posts
    1,654
    Quote Originally Posted by smokeyangel View Post
    explain without a pile of binary. So let's do that ... Take 290, which is 100100010.
    Showing 16 bits

    1st loop: x = x & (x-1) = 0000000100100010 & 0000000100100001 = 000000100100000
    2nd loop: x = x & (x-1) = 0000000100100000 & 0000000100011111 = 000000100000000
    3rd loop: x = x & (x-1) = 0000000100000000 & 0000000011111111 = 000000000000000

  5. #5
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    Not to be beaten on 'who can post the most binary today', I assulted a double and make it pretend to be an integral value for 10 mins. Here's what 1.2548246 looked like

    Code:
    0b11111111110100000100111100001011110101101100110111010111100000
    0b11111111110100000100111100001011110101101100110111010111000000
    0b11111111110100000100111100001011110101101100110111010110000000
    0b11111111110100000100111100001011110101101100110111010100000000
    0b11111111110100000100111100001011110101101100110111010000000000
    0b11111111110100000100111100001011110101101100110111000000000000
    0b11111111110100000100111100001011110101101100110110000000000000
    0b11111111110100000100111100001011110101101100110100000000000000
    0b11111111110100000100111100001011110101101100110000000000000000
    0b11111111110100000100111100001011110101101100100000000000000000
    0b11111111110100000100111100001011110101101100000000000000000000
    0b11111111110100000100111100001011110101101000000000000000000000
    0b11111111110100000100111100001011110101100000000000000000000000
    0b11111111110100000100111100001011110101000000000000000000000000
    0b11111111110100000100111100001011110100000000000000000000000000
    0b11111111110100000100111100001011110000000000000000000000000000
    0b11111111110100000100111100001011100000000000000000000000000000
    0b11111111110100000100111100001011000000000000000000000000000000
    0b11111111110100000100111100001010000000000000000000000000000000
    0b11111111110100000100111100001000000000000000000000000000000000
    0b11111111110100000100111100000000000000000000000000000000000000
    0b11111111110100000100111000000000000000000000000000000000000000
    0b11111111110100000100110000000000000000000000000000000000000000
    0b11111111110100000100100000000000000000000000000000000000000000
    0b11111111110100000100000000000000000000000000000000000000000000
    0b11111111110100000000000000000000000000000000000000000000000000
    0b11111111110000000000000000000000000000000000000000000000000000
    0b11111111100000000000000000000000000000000000000000000000000000
    0b11111111000000000000000000000000000000000000000000000000000000
    0b11111110000000000000000000000000000000000000000000000000000000
    0b11111100000000000000000000000000000000000000000000000000000000
    0b11111000000000000000000000000000000000000000000000000000000000
    0b11110000000000000000000000000000000000000000000000000000000000
    0b11100000000000000000000000000000000000000000000000000000000000
    0b11000000000000000000000000000000000000000000000000000000000000
    0b10000000000000000000000000000000000000000000000000000000000000
    0b0
    37 set bits, apparently. There, now I have enriched everyone's life I shall head off. Probably into the slightly black and white matrix above.

    [code]
    Last edited by smokeyangel; 12-01-2013 at 02:41 AM.

  6. #6
    Registered User
    Join Date
    Apr 2013
    Posts
    1,654
    Quote Originally Posted by smokeyangel View Post
    Not to be beaten on 'who can post the most binary today'
    That wasn't my point. I wanted to make clear that it was the & (binary) and operation with x and (x-1) that is clearing the least significant 1 bit.

  7. #7
    Registered User
    Join Date
    Mar 2010
    Posts
    582
    It wasn't a serious comment on my part -- I was just being silly. I didn't even think when I wrote it. Anyway, apologies for the misunderstanding.

Popular pages Recent additions subscribe to a feed

Similar Threads

  1. Understanding Bitwise Operators in C
    By Andersonsacanno in forum C Programming
    Replies: 8
    Last Post: 01-06-2013, 04:48 AM
  2. Bitwise setbits function (knr 2-6)
    By olbas in forum C Programming
    Replies: 17
    Last Post: 03-10-2010, 07:40 AM
  3. Understanding Bitwise Manipulation in c
    By MrWannabe in forum C Programming
    Replies: 18
    Last Post: 09-25-2009, 08:33 AM
  4. need help understanding this function
    By Lince in forum C Programming
    Replies: 4
    Last Post: 08-04-2007, 10:29 AM
  5. bitwise OR in function parameters
    By Unregistered in forum C++ Programming
    Replies: 6
    Last Post: 07-26-2002, 05:36 PM