an awsm tutorial over bit-manipulation

https://www.hackerearth.com/practice/notes/bit-manipulation/

Dark Mode

Arjun
asked
in Programming
Oct 19, 2016

1,132 views
9 votes

What is the following function doing?

unsigned int foo(unsigned int x) { unsigned int c = sizeof x; c <<= 3; if(x == 0) return c; c--; while(x = x & x-1) c--; return c; }

- Counting the number of bits in the binary representation of x
- Counting the number of set bits in the binary representation of x
- Counting the number of unset bits in the binary representation of x
- None of the above

an awsm tutorial over bit-manipulation

https://www.hackerearth.com/practice/notes/bit-manipulation/

0

13 votes

Best answer

1. unsigned int foo(unsigned int x){ 2. unsigned int c = sizeof x; 3. c <<= 3; 4. if(x == 0) return c; 5. c--; 6. while(x = x & x-1) c--; 7. return c; 8. } line no 2 : c = no of bytes for x. line no 3 : c<<=3 is c*8 which is converting Byte into bits. line no 6 : counting no of 1s and decrementing c value by 1. c will be decremented as many times as no of 1s will be in x. line no 7 : return c i.e. no of 0s or no of Unset bit in x.

0

0

edited
Jan 9, 2017
by Ritwik Mishra 1

line no 4 : c<<=3 is c*8 which is converting Byte into bits. line no 6 : decrementing c because while will run only k-1 times, where k is no of 1s in x line no 7 : counting no of 1s and decrementing c value by 1. c will be decremented k-1 times, where k is no of 1s in x. so overall after while loop, total no of 1s in x will be subtracted from c line no 8 : return c i.e. no of 0s or no of Unset bit in x.

1

2

2 votes

Let's take a *bad* number, ie, not a power of 2. Let's take 53.

In binary, 53 = 110101. (4 ones, 2 zeroes)

c <<= 3;

will give us the number of bits required to represent 53 in binary. See Digvijay Pandey's answer.

Now,

while(x = x & x-1) c--;

When x is bitwise-ANDED with (x-1), it is a property that this result would contain one less 1 than x.

53 AND 52 = 110101 AND 110100 = 110100 (4 1's reduced to 3 1's)

110100 is 52. So,

52 AND 51 = 110100 AND 110011 = 110000 (3 1's reduced to 2 1's)

110000 is 48, So

48 AND 47 = 110000 AND 101111 = 100000 (2 1's reduced to 1 1)

100000 is 32, So

32 AND 31 = 100000 AND 011111 = 0 (1 1 reduced to 0 1's)

It took 4 steps. At each step we decremented c.

=> We decremented c four times.

=> From the bits required to represent 53, we subtracted 4 bits.

=> Number of bits remaining is the count of 0's in 53.

**Option C**