Where can I find a bit shifting guide for C?

Question

I have looked at http://stackoverflow.com/questions/141525/absolute-beginners-guide-to-bit-shifting 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 really do not understand it but I want to learn it, so any help would be appreciated.

I am learning the 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.

EDIT here's the exersices 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 thatbegin 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 poisiton 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, Use this observation to write a faster version of bitcount

These are exercises from the k&R (the c programming language) book its the best c book there is but I am having trouble understanding bitshifting so I am having problems with these exercises.

Answer 1

The guide you linked to is really good. What is it you don't understand about bit-shifting?

I don't know what the K&R is, so I can't help you there.

Can you be more specific with the question, and I can edit to be more specific about the answer.

Answer 2

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 3

Your 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's some basics to test yourself against to make sure you understand

// 1234 in hex, 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 4

If you have the money (and the time), grab a copy of Hackers Delight. 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 5

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 ind 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 (e.g. 0xFF for n=8, 0x7F for 7 and so on), or you can use a combination of setting bit 0 and lef-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 6

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 7

edit: just saw someone else already posted my suggestion to buy a copy of hacker's delight. :)

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.

Answer 9

There's a great introduction to bitwise operators right here on stack overflow already: Here

Answer 10

Write the bits on paper and 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.

What you will find and what the K&R exercises are about are 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 1 bit to the right in this manner would be an 0xE, because the lsbit was a 1 so shift 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. Lets 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, lets 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 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, the younger folks with modern processors dont 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 intead. 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 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, 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 lsbit so 0bQWER shifted left one is 0bWER0. And that makes sense -4 shifted left one is 0xF8 which is -8, -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, then go abstract. Want to rotate 0x1234 to the right one bit lets 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 11

Bit Twiddling Hacks

Answer 12

Here is a basic guide that I found some time back at AVRFreaks. That will show you the fundamentals, and then you can go on with the other tutorials.

• http://www.avrfreaks.net/index.php?name=PNphpBB2&amp;file=viewtopic&amp;t=37871