Home C Programming All Sections
 
A Brief Look at Bitwise Operations
Bitwise operations are a type of simple change to a piece of memory. They can range anywhere from a SHIFT or ROTATE of the bits all the way to a logical operation such as AND, OR and XOR. In this article, a brief description of each of the mentioned operations and some uses for each will be discussed

Examples
bitflags.c
c-case.c
shift.c
 


Hosted by...
Linode
 

Sponsored Links

 

Logical operations

Logical operations are just what they sound like - operations that use logic. Logical operations include AND, OR, and XOR (eXclusive OR). These three commands have tons of uses in programming - including but not limited to - simplifying logic flags and changing case of ASCII letters through bit masking.

The AND operation looks for two TRUE bits. If one of both bits are FALSE, AND returns a FALSE. If both bits are TRUE, AND returns a TRUE.

The OR operation looks for at least one TRUE bit in it's arguments. If both are TRUE, or if just one is TRUE, OR will return a TRUE. If both bits are FALSE, OR will return a FALSE.

The XOR operation returns a TRUE if only one of it's two arguments is TRUE. If both bits are TRUE or both bits are FALSE, XOR will return a FALSE. If only one of the two bits is TRUE, XOR will return a TRUE.

A table of these three logical operations can be found below.

Operation Value 1 Value 2 Result
AND FALSE FALSE FALSE
AND FALSE TRUE FALSE
AND TRUE FALSE FALSE
AND TRUE TRUE TRUE
OR FALSE FALSE FALSE
OR FALSE TRUE TRUE
OR TRUE FALSE TRUE
OR TRUE TRUE TRUE
XOR FALSE FALSE FALSE
XOR FALSE TRUE TRUE
XOR TRUE FALSE TRUE
XOR TRUE TRUE FALSE

So here you are, looking at the truth table and wondering how this table you learned about in second grade will make your programming tasks easier. Two very useful applications of our logical operations are (as mentioned before) boolean flags and changing ASCII alphabetical cases. Examples of these two methods can be seen in bitflags.c and c-case.c.


Shift and Rotate

The shift/rotate operations are quite similar to each other. In these two bitwise operations, the position of our bits is moved but the order of bits is preserved. The only difference between these two operations is what happens to bits that are shifter out of the memory. A rotate command will put the bit that is pushed off back into the memory in the place that is on the opposite end of our memory. A shift operation simply gets rid of the end bit (not really, but we'll discuss that in a little) and places a 0, 1, or random bit on the opposite end depending on the architecture/processor/assembler. These may not seem like such impressive tasks, but they can save us tons of time in certain operations.

Shift and rotate can be used in either the right or left directions and for any number of bits. Some architectures even allow a 'rotate through carry' which is simply moving the fallout bit into the carry flag. When this happens, it takes one shift more than the size of a register to bring you original number back into the register.

Now that we know all of this, what are some things we can do with it? Imagine the bits of 0x2A [0010 1010]. In the table below, we will shift these bits in both directions.

Operation Hexadecimal Binary Decimal
None 0x2A 0010 1010 42
Right shift by 1 0x15 0001 0101 21
Left shift by 1 0x54 0101 0100 84

Did you notice what happened to the value after it was shifted left by one bit? Did you notice what happened to the value after it was shifted right by one bit? The left shift operation multiplied our number by 2 and our right shift divided our number by 2.

What happens if we shift by two bits?

Operation Hexadecimal Binary Decimal
None 0x2A 0010 1010 42
Right shift by 2 0x0A 0000 1010 10
Left shift by 2 0xA8 1010 1000 168

The results of a two bit shift are different than a one bit shift as one would have expected. Do you notice anything interesting about these shifts? The two bit left shift produced a number 4 times greater than our original number while the 2 bit right shift almost produced a number 4 times smaller than our original number. The right-most bit of the number was shifted out of our bit sequence, so we lose some accuracy in our result. However, if you were to divide 42 by 4 in c or c++, the result would be 10. This is due to the fact that we are dealing with integers. Fractions can not be saved in this type of numbers. If a one bit shift caused a number to be multiplied/divided by 2 and a two bit number caused a number to be multiplied/divided by 4, what would be your guess for a three bit shift operation? Assuming no bit overflow, a three bit shift will multiply/divide our number by 8. A general rule is that:

A n bit left shift will multiply by 2n. A n bit right shift will divide by 2n.


Conclusions

To the inexperienced programmer, bitwise operations may seem a bit scary. These operations, however, are actually fairly simple to use. Once mastered, bitwise operations (especially logical operations) can be very helpful. A programmer should have many tools in his belt - one of which is certainly a knowledge of bitwise operations.

 
Manpages About Webmaster