Shift operators shift the bits in an integer variable by a specified number of positions. The
<< operator shifts bits to the left, and the
>> operator shifts bits to the right. The syntax for these binary operators is
x << n and
x >> n Each operator shifts the bits in x by n positions in the specified direction. For a right shift, zeros are placed in the n high-order bits of the variable; for a left shift, zeros are placed in the
n low-order bits of the variable.
Here are a few examples:
Binary
00001000 (decimal 8) right-shifted by 2 gives
00000010 (decimal 2).
Binary
00001000 (decimal 8) left-shifted by 3 gives
01000000 (decimal 64).
One of the application of shift operation is to count the number of bits set in an unsigned integer.
For example: f(0) = 0, f(1) = 1, f(2) = 1, f(3) = 2.
More information @
Wikipedia
Option 1: In a while loop, increment a counter if the last bit in the unsigned integer is 1 all the while right shifting the integer in each iteration of the while loop.
// C program to count the number of bits set in an integer
#include<stdio.h>
int main()
{
unsigned int i, b[32] = {0};
int j = 31, count = 0;
printf("\nEnter the unsigned integer:");
scanf("%d", &i);
while(i != 0)
{
// Bitwise AND operation b/w i & 0x00000001 is 1
// if the last bit of i is 1 and 0 if the last
// last bit is 0
b[j] = i & 0x00000001;
// Increment count whenever the bit is 1
if(b[j] == 1)
count++;
j--;
// Right shifting i by 1 to get the next bit
i = i >> 1;
}
printf("\nThe number of bits set in %d is %d", i, count);
// The array b gives the binary representation of i
printf("\nThe binary representation of %d is ", i);
for(i = j + 1; j < 32; j++)
printf("%d", b[j]);
return 0;
}
Brian Kernighan's method: Published in 1988, the C Programming Language 2nd Ed. (by Brian W. Kernighan and Dennis M. Ritchie) mentions this in exercise 2-9. On April 19, 2006 Don Knuth pointed out to him that this method "was first published by Peter Wegner in CACM 3 (1960), 322. (Also discovered independently by Derrick Lehmer and published in 1964 in a book edited by Beckenbach.)".
long count_bits(long n) {
unsigned int c; // c accumulates the total bits set in v
for (c = 0; n; c++)
n &= n - 1; // clear the least significant bit set
return c;
}
Use built-in functions in compilers: GCC has the following built-in function to count the number of bits. The compiler can generate a single
POPCNT instruction in the best case or generate a call to a function to count the number of bits in the worst case.
int __builtin_popcount (unsigned int x);
SWAR Algorithm: This uses a divide & conquer algorithm where the problem of summing the number of bits set in a 32 bit unsigned integer is divided into two problems of summing the number of bits set in a 16 bit integer. This strategy is applied recursively resulting in log
2(32) = 5 steps. -
From Hacker's Delight, p. 66, Figure 5-2
int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}
These are some of the ways to tackle this problem.
References:
Written by Munia Balayil
1 + 1 = 2