Bit-wise operations in C

Counting Bits

How many different integers between low and high (including low and high) have exactly N bits of 1 in the two's complement representation? That's the question to be answered in this problem.

Example

The problem is pretty clear. For example, suppose low is 5, high is 14, and N is 2. If we look at the two's complement binary representation of the integers between 5 and 14 and identify those with exactly 2 one bits, we find that there are five such numbers (identified by the left-pointing arrows). Note that the 28 high-order bits in the following example are all zeros.

50101 101010 

60110 111011

70111 121100 

81000131101

91001 141110

So the answer in this case would be 5.

Input

There will be multiple input cases to consider. For each case ask the user for low (the low value), high (the high value), and N (the number of bits). low and high will each be in the range -2147483648 to +214483647, and N will be in the range 1 to 32. Start with low and work up to high, counting the number of 1 bits in each number. If the number of 1 bits is equal to N, count the number. When you have finished with the last number (high), print the result. The examples below have the correct answers for the given inputs. When the user enters 0 for low (the low value), quit.

How to do it: We will look at an 8-bit number instead of a 32-bit number to make the example shorter. Consider the number 19 as an 8-bit 2s complement number: 0001 0011.

Step 1:

Start with the rightmost bit of 19. AND it with the number 1 (0000 0001):

0001 0011 // 19

0000 0001 // 1 (our "mask")

0000 0001 // 1 (the result of ANDing 19 and 1)

Because the result is not 0, there is a 1 in this bit location of the number 19. Our count of 1 bits is now 1.

Step 2:

Now move to the next bit (shift your mask—the number 1—to the left one position):

0001 0011 // 19

0000 0010 // 2 (our "mask")

0000 0010 // 2 (the result of ANDing 19 and 2)

Because the result is not 0, there is a 1 in this bit location of the number 19. Our count of 1-bits is now 2.

Step 3:

Now move to the next bit (shift your mask—now the number 2—to the left one position):

0001 0011 // 19

0000 0100 // 4 (our "mask")

0000 0000 // 0 (the result of ANDing 19 and 4)

Because the result is 0, there is NOT a 1 in this bit location of the number 19. Our count of 1-bits is still 2.

Step 4:

Now move to the next bit (shift your mask—now the number 4—to the left one position):

0001 0011 // 19

0000 1000 // 8 (our "mask")

0000 0000 // 0 (the result of ANDing 19 and 8)

Because the result is 0, there is NOT a 1 in this bit location of the number 19. Our count of 1-bits is still 2.

Step 5:

Now move to the next bit (shift your mask—now the number 8—to the left one position):

0001 0011 // 19

00010000 // 16 (our "mask")

0001 0000 // 16 (the result of ANDing 19 and 16)

Because the result is not 0, there is a 1 in this bit location of the number 19. Our count of 1-bits is now3.

Step 6:

Now move to the next bit (shift your mask—now the number 16—to the left one position):

0001 0011 // 19

0010 0000 // 32 (our "mask")

0000 0000 // 0 (the result of ANDing 19 and 32)

Because the result is 0, there is NOT a 1 in this bit location of the number 19. Our count of 1-bits is still 3.

Step 7:

Now move to the next bit (shift your mask—now the number 32—to the left one position):

0001 0011 // 19

0100 0000 // 64 (our "mask")

0000 0000 // 0 (the result of ANDing 19 and 64)

Because the result is 0, there is NOT a 1 in this bit location of the number 19. Our count of 1-bits is still 2.

Step 8:

Now move to the next bit (shift your mask—now the number 64—to the left one position):

0001 0011 // 19

1000 0000 // 128 (our "mask")

0000 0000 // 0 (the result of ANDing 19 and 128)

Because the result is 0, there is NOT a 1 in this bit location of the number 19. Our count of 1-bits is still 3.

The process is the same for a 32-bit number. You just make 32 passes through the loop instead of 8.

Here is a video on the operators needed for this assignment.

Output

For each input case, display the number of 1 bits.

Low? 5

High? 14

Number of 1 bits? 2

There are 5 numbers with 2 one bits between 5 and 14.

Low? 5

High? 14

Number of 1 bits? 3

There are 4 numbers with 3 one bits between 5 and 14.

Low? -1

High? 1

Number of 1 bits?

There is1 number with 1 one bits between -1 and 1.

Low? -1

High? 1

Number of 32 bits?

There is1 numbers with 32 one bits between -1 and 1.

Low? -2147483648

High? -2147483636

Number of 1 bits? 3

There are 6 numbers with 3 one bits between -2147483648 and -2147483636.

Low? 0

Useful C skills for this problem

In addition to understanding how two's complement numbers are represented, you should be familiar with the following C bitwise operators: &, |, ^, !, >, <.