Where can I find a bit shifting guide for C?

Question

I have looked at What are bitwise shift (bit-shift) operators and how do they work?, but I still find the concept of bit shifting difficult to understand.

Can someone point me in the direction of a more basic guide to bit shifting in C? I expect it will be something really long since it will need to cover the whole subject.

I am learning the The C Programming Language (AKA K&R), and that is what this is for, so I can do the exercises. I understand the basics, but I still cannot do correct bit shift operations.

Here are the exercises from K&R that have stumped me

Exercise 2-6: Write a function setbits(x, p, n, y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.

Exercise 2-7: Write a function invert(x, p, n) that returns x with the n bits that begin at position p inverted (i.e., 1 changed into 0 and vice versa), leaving the others unchanged.

Exercise 2-8: Write a function rightrot(x, n) that returns the value of the integer x rotated to the right by n bit positions

Exercise 2-9: In a two's complement number system, x &= (x-1) deletes the rightmost 1-bit in x. Explain why, and use this observation to write a faster version of bitcount.

These are exercises from the k&R (the C programming language) book. It's the best C book there is, but I am having trouble understanding bit shifting, so I am having problems with these exercises.

Answer 1

Bit shifting is nothing but what it literally means: shifting all bits in a given sequence left or right.

All you have to remember is that every decimal number (like 6, 7, 3, 2) is represented as a sequence of bits in the memory of the computer. So if you find something like this in a piece of C code:

(7 >> 1)

it means that the bits in the underlying binary representation of 7 are to be shifted right by 1 position.

I think the explanation in the link you cite is pretty clear. Maybe writing down a sequence of bits on a paper yourself and manipulating them as in the cited link can help.

Or perhaps you don't possibly yet have the understanding how computers work with numbers internally. In that case, before learning bit shifting, you need to read about that.

Answer 2

You're going to need more tools in your toolkit to answer those questions than shifting.

I think you'll need to start very basic about how numbers are represented in binary. Then you'll want to think about how to set and clear specific bits in that number, or a group of bits at the same time. You'll need to know how to test to see if a certain group of bits is set and about masking. You'll have to be able to do all the above with the bitwise operators and, or, xor, inversion, etc. operators.

Then you'll want to know about shifting -- moving bits left and right by a specific number of spaces. You'll want to know what happens to the bits left "empty". Is it filled with a 1 or a 0? When is it filled with a 1 or 0?

Googling "bitwise operations tutorial" seems to have come up with some promising results to begin with. But here are some basics to test yourself against to make sure you understand

// 1234 in hexadecimal. Do you understand this is not 1234 in decimal? Do you understand
// how specifying in hex makes it easier to think about the binary representation?
unsigned short i = 0x1234;
// Flip all the bits in 0x1234
printf("%04x", ~i);

// Test - Is the most significant bit set?
// mask is a binary number with the most significant bit set. Do
// you understand why this is so?
unsigned short mask = 0x8000;
if ((mask & i) == mask)
{
    printf("bit set!");
}
else
{
    printf("bit cleared!");
}

// Set the most significant bit
i = i | mask;
printf("Set the MSB of i, check it out: %i\n", i)

// Set the second most significant bit
// Do you see how by shifting mask right one it becomes the next most significant bit?
i = i | (mask >> 1);

Good Luck!

Answer 3

Write the bits on paper, think about erasing them from one end, and adding more on the other. Not unlike elementary school and moving the decimal point around when multiplying by 10.

All of your C functions are going to shift zeros in.

So

x = y << 3;

means shift left three bits and the new bits on the right are all zeros. The three bits that were on the left go into the "bit bucket":

x = z >> 2

Lose the two bits on the right and add two zeros on the left.

You will find, and what the K&R exercises are about, the missing functions. Among the processor types out there you have far more shifting capabilities than you do in C or any other high level language.

You have rotate functions where the bit shifted off of one end gets shifted in the other.

So the number 0xD rotated one bit to the right in this manner would be an 0xE, because the least significant bit was a 1 so shifting 1101 to the right, the 1 on the right becomes a 1 on the left 1110.

Sometimes you rotate through the carry bit in the ALU. Let’s say the carry bit had a zero in it and you rotated 0xD one bit 0 1101 leaves 1 0110 a 0x6. Rotate that one more, 0 1011 and you get a 0xB and so on.

Why would you ever rotate through the carry bit you ask? For bigger numbers, say you have four bit registers and want to do an 8 bit shift, let's say each of the letters are bits a bcde fghi where a is the carry bit and the other two groups of four are four bit registers. Start by rotating the left register through the carry e abcd fghi, and then rotate the right register through the carry i abcd efgh. Pretty cool; we just did an 8 bit shift with a 4 bit shift function.

If you had cleared the carry bit before starting (often there is an instruction for this or you can always do something like add 0+0 or something else guaranteed to clear that bit) you would have

i 0bcd efgh

which is not unlike what a C shift function would do if you are say on a 32 bit instruction set operating on a 64 bit number.

The processors often have the C like shifts where a zero is shifted in, shift abcd left one gives bcd0 shift abcd right two gives 00ab.

And this leads to some problems with the younger folks with modern processors ... think about such things because an integer divide is both supported on their processor and can operate in a single clock cycle. Back before we had divide or when divide was dozens to hundreds of clocks, but a shift was a single clock you would do all of your power of 2 divides or multiplies using shifting instead. Take the number 0x0D shift that left two you get 0b00001101 << 2 = 0b00110100 or 0x34. 0xD is 13 decimal and 0x34 is 52 decimal. 52 is four times more than 13. Four is 2 to the power of 2. Shifting by two is the same as multiplying by four.

This works both ways; 0x34 shifted right 2 is 0xD, but here is the problem. When you get into negative numbers, take the number minus 4 0xFC, and now divide that by two. Using C 0xFC >> 1 would give 0x7E, but 0x7E is +126 decimal. How does -4/2 = 126?

The problem is that C shifts in zeros. You will find some processors have an arithmetic shift which is different than a logical shift. The arithmetic shift keeps the upper-most bit, so if you are working with a signed number, like 0bQWER, and you arithmetically shifted that right one bit you get 0bQQwe. The upper-most bit both shifts into the next bit and stays where it was.

Shift again 0bQQQW, and so on. Now an arithmetic shift left will shift in zeros and not the least significant bit, so 0bQWER shifted left one is 0bWER0. And that makes sense. -4 shifted left one is 0xF8 which is -8, and -4 times two is -8, so that is right.

So you will find that some processors only have an arithmetic shift right, but not a left. Some allow you to specify an asl, but when they assemble it replace it with an lsl (logical shift left) and who knows some may actually have a separate opcode even though it is the same function. I assume there may be some that have an asl and an asr and lsr, but no lsl.

Just use paper and pencil and figure things out. Start with real numbers as examples, and then go abstract. Want to rotate 0x1234 to the right one bit, let's say?

0001001000110100  write out the bits
x0001001000110100 shift right one
0000100100011010  because this is a rotate fill in the new bit with the bit that fell off on the prior operation

Want to now shift two bits to the right

0000100100011010
xx0000100100011010
1000001001000110

How would I do a single bit rotate in C?

unsigned int rotate_right_one ( unsigned int x )
{
  unsigned int y;
  y = x & 1;  // Save the bit that is about to fall off the right
  x >> = 1;  // Logical rotate one bit
  x |= y<<31; // This assumes that unsigned int is 32 bits.
  return(x);
}

To rotate more you can simply call this function multiple times or think about the mask and shift above and how would that work for more than one bit.

Also note that some processors only have one rotate function. For example, think about this. I have a four bit register and I rotate 5 bits. What do I get?

abcd
bcda  first rotate
cdab  second
dabc  third
abcd  fourth
bcda  fifth

What does a single rotate left look like?

abcd
bcda  one bit left.

Five right on a four bit register is the same as one left 5-4=1. Like the asl, some processors will let you code the operation, but the assembler replaces that operation with the other rotate using nbits-shift as the rotate amount.

For some people logical bit operations are as tough as pointers to understand, but it is a fundamental and if you learn it and use it you will be way out ahead of your competition or those around you.

Here is an example that counts the number of bits in some variable:

for(count=0, r=1; r; r<<=1) 
    if(r&some_variable) 
        count++;

Understand that line of code and you are well on your way to both learning C and the logical bit operations.

Answer 4

Taking 2-6 as an example, I used the values 17, 4, 3, 15.
So:

x = 17 or 10001

p = 4

n = 3

y = 15 or 01111

Using my example numbers what we need to do here is take the three ls bits from y (111) and insert them into x starting at position 4. This will give us 11111 or 31. We need to clear the 3 bits in x starting at position four, clear all of the bits in y except for the rightmost 3 bits, move them to position four and OR the two values together.

1st: Shift all ones to the left n positions ~0 << n = 1111111111111000

2nd: Place all ones at the rightmost n positions ~(~0 << n) = 0000000000000111

3rd: Shift these n 1 bits to position p and set n bits to zeros starting at position p. ~(~(~0 << n) << (p-n)) = 1111111111110001

4th: And this mask with x to clear the n bits of x at position p = 10001

(I am sure that everyone realizes that all we did is get right back to our starting number, but we have to do this in order to tell the program what position we want to start at, and how many bits we would like to work with. What if p is 6 and n is four?)

Next clear all bits in y except for the rightmost n bits:

1st: ~(~0 << n) places all ones in the rightmost n positions. 0000000000000111

2nd: y & ~(~0 << n) Select the rightmost n bits of y 0000000000000111

3rd: (y & ~(~0 << n)) << (p-n) Place n bits of y at position p 0000000000001110 Finally OR the two outcomes together

0000000000010001 = 17

0000000000001110 = 7 OR=

0000000000011111 = 31

The result becomes:

return x & ~(~(~0 << n) << (p-n)) | (y & ~(~0 << n)) << (p-n);

I am sorry if this is at all hard to read. I was somewhat limited in my formatting ability. (I am sure this is my fault) I hope that this helps, I have been stuck on this particular exercise for quite a while, and finally came up with this solution today, after looking at this very thread, so I figured that I would post the right answer, as well as, an explanation as to why it is the right answer, which is something that I have found lacking in many answers that I have seen.

Answer 5

If you have the money (and the time), grab a copy of Hacker's Delight (by Henry S. Warren). It is probably the best bit shifting guide around. It will take you through simple shifts (and other manipulation techniques) all the way through Gray codes and more...

Answer 6

Let's go through one exercise, for a sample.

Exercise 2-6: Write a function setbits(x, p, n, y) that returns x with the n bits that begin at position p set to the rightmost n bits of y, leaving the other bits unchanged.

Let's keep in mind that the least significant bit is bit 0 (is at position 0).

Here is the pseudocode:

1. Move the bits p to p+n in x to position 0 to n. That's where you right-shift.
2. Prepare a bit mask that will turn anything from bit n to the highest bit into 0s. You can use a lookup array for this (for example, 0xFF for n=8, 0x7F for 7 and so on), or you can use a combination of setting bit 0 and left-shifting in a loop.
3. Apply the bit mask to x using &. All the bits we don't care about in x are now 0.
4. Invert the bit mask. We now have a bunch of 1s at the high end, and a bunch of 0s at the low end. The bits we want to change in y all have 0s in bit mask.
5. Apply the bit mask to y using & . All the bits in y that we will replace with bits in x are now set to 0, and the bits that we don't want to change are unchanged.
6. Set the bits we want to change in y by combining x and y using |. This is the crucial point - go over what's happening with a pen and paper. The bits in x that were set to 0 in (3) will not affect the corresponding bits in y. The bits in x that were not affected by (3) will combine with 0s in y (0s because of step5), setting the resulting bit to the value it had in x.

Answer 7

Keep in mind that nearly all of those exercises have a straightforward solution that can be written with functions int IsBitSet(int i, int n); int SetBit(int i, int n); and combinations of << and >>. The straightforward solutions are nearly all worst case, but are far easier to implement and read. This is kind of like implementing multiplication in terms of addition or addition in terms of increment.

Answer 8

Let's try 2-6, to give you a taste of how bit operations work, and then see if it makes sense.

int setbits( int x, int p, int n, int y )
{
    int bitmask = ~0, y_right = 0; 

    /* Ok, first let's get y's rightmost bits.
     * Take our bitmask, shift it left by n bits, leaving the least significant
     * n bits as 0. Then, flip the bitmask so the rightmost n bits become 1, and the
     * leftmost n bits become 0.
     *
     * Then, AND this bitmask with y, to yield y's n rightmost bits.
     */
    bitmask = ~( bitmask << n );
    y_right = bitmask & y;

    /*
     * Ok, now let's use y_right as our bitmask for x.
     * Shift y_right to the left to *begin* at position p.
     */
     y_right <<= p - n;
     x |= y_right;

     return x;
}

Note: the above may be completely incorrect as I haven't tested it, but it should give you a decent idea to start with.