C bit wise operators

As an old school C programmer, I use all these operators somewhat frequently. I thought I'd write this tutorial to illustrate typical situations where I use them, and provide some sample code snippets.

% MODULO

The modulo operator gives you the remainder after integer division. For example, 16 % 3 is 1. Why? If you divide 16 by 3, you get 5, with a 1 left over. The "left over" part is what the module operator gives you. If you use modulo with an ascending series of numbers, it produces a characteristic repeating "stripe" pattern that goes from 0 to N-1, like so:

0 % 3 == 0 1 % 3 == 1 2 % 3 == 2 3 % 3 == 0 4 % 3 == 1 5 % 3 == 2 6 % 3 == 0 7 % 3 == 1 etc. 

For positive numbers, the results of modulo are predictable.

Unfortunately, for negative numbers, the results vary, depending on the language. Javascript has the following pattern, which is arithmetically correct:

-1 % 3 == -1 -2 % 3 == -2 -3 % 3 == 0 -4 % 3 == -1 -5 % 3 == -2 -6 % 3 == 0 -7 % 3 == -1 etc. 

But other languages, like Perl, have the following pattern, which essentially continues the pattern you see in the positive numbers:

-1 % 3 == 2 -2 % 3 == 1 -3 % 3 == 0 -4 % 3 == 2 -5 % 3 == 1 -6 % 3 == 0 -7 % 3 == 2 etc. 

You can make arguments for either case, since they both have their uses. Since I personally have a hard time remembering these kinds of language-specific details (and I program in a variety of different languages), I tend to avoid using Modulo with negative numbers in my work. For now, I'll concentrate on the positive numbers, and then show a trick which avoids the problem with the negative numbers.

That basic stripe pattern of 0,1,2, 0,1,2, 0,1,2... is a very useful thing, and I tend to employ it when I have software that has right and left-arrow navigation. For example, there might be a user-interface element which contains a "right arrow" which takes you to the "next page". If I'm on the last page, I often want to "wrap around" to the first page. "Wrap around" is an ideal use for the modulo operator.

If the page numbers are numbered 0 thru N-1 (where N is the number of pages), and the current page number is represented by curPage, then pressing the right arrow can invoke a script which does something like this:

curPage = (curPage + 1) % N; 

If you were not familiar with the modulo operator, you might code this like so:

curPage = curPage + 1 if (curPage == N)   curPage = 0; 

If N is 3, both code snippets produce the following transitions:

0 -> 1 1 -> 2 2 -> 0 

... But the modulo version is only one line. This to me, is a classic use of the modulo operator. Typically, I will internally represent page number using a zero-based number, to make it easier to use the modulo operator in this way. But even if your page numbers start at 1, you can still use modulo, by changing the forumula as follows:

curPage = ((curPage-1)+1 % N) + 1; 

which simplifies to:

curPage = (curPage % N) + 1; 

If N is three, this produces the following transitions.

1 -> 2 2 -> 3 3 -> 1 

Now let's consider how you can handle a left-arrow, which takes you to the previous page, and also loops around from the first page to the last page. If your page numbers are 0 - N-1, you might start with the following formula:

curPage = (curPage - 1) % N; 

But notice there is a problem if curPage is set to 0 (zero), depending on the behavior of the modulo operator. In the Perl implementation of Modulo, this code works (which is probably why Perl implemented Modulo that way), but in the Javascript implementation of Modulo, which is arithmetically correct, it does not work, so you have to special case it:

if (curPage == 0)   curPage = N-1; else   curPage = (curPage - 1) % N; 

Here's a cool trick that avoids the special case:

curPage = (curPage + (N-1)) % N; 

Notice this still has the following transition table for N=3:

0 -> 2 1 -> 0 2 -> 1 

If your page numbers start at 1, then convert it to a zero-based number first (by subtracting one), perform the operation, and then convert it back (by adding one):

curPage = ((curPage-1) + (N-1)) % N + 1; 

which has the following transition table for N=3:

1 -> 3 2 -> 1 3 -> 2 

You can generalize both of these directions by using a delta variable, which keeps track of the direction of travel. If traveling to the left, delta = -1, if traveling to the right, delta = 1. In this case, you would use the following code for zero-based page numbers (from 0 to N-1):

function gotoNextPage(delta) {   curPage = (curPage + N + delta) % N; } 

and the following code for one-based page numbers (from 1 to N):

function gotoNextPage(delta) {   curPage = ((curPage-1) + N + delta) % N + 1; } 

You can use modulo anytime where that "stripe" effect is useful - even for making stripes in graphics software! I've also used it for game software where a spaceship needs to wrap around the screen - reappearing on the left side after disappearing on the right. This looks something like this:

spaceship.x = (spaceship.x + screenWidth + horizontalSpeed) % screenWidth; spaceship.y = (spaceship.y + screenHeight + verticalSpeed) % screenHeight; 

& Bitwise AND
| Bitwise OR
~ Bitwise NOT

Here are some tables showing the effect of these bitwise logic operators. I've included the ^ XOR operator as well, which I'll discuss further down.

0 & 0 == 0 0 & 1 == 0 1 & 0 == 0 1 & 1 == 1  0 | 0 == 0 0 | 1 == 1 1 | 0 == 1 1 | 1 == 1  0 ^ 0 == 0 0 ^ 1 == 1 1 ^ 0 == 1 1 ^ 1 == 0  ~0 == 1 ~1 == 0 

These operators are called "bitwise" because they are applied to every single bit in the operands. So for example, in binary

00101101 & 00011100 == 00001100 

which in decimal comes to

45 | 28 == 12 

I most commonly use these bitwise logic operators for maintaining a set of flags, which are stored in a single numeric variable. To make sense of these operators, you have to visualize the binary representation of the numbers involved.

Let's say I have a game which involves different characteristics of animals, which are tracked using flags.

kHasTeeth   = 1; kHasFur     = 2; kHasScales  = 4; kHasLungs   = 8; kHasGills   = 16; kHasTusks   = 32; 

Note that these flags corresponding to single bits in binary numbers:

          // decimal    binary kHasTeeth   = 1;    // 00000001 kHasHair    = 2;    // 00000010 kHasScales  = 4;    // 00000100 kHasLungs   = 8;    // 00001000 kHasGills   = 16;   // 00010000 kHasTusks   = 32;   // 00100000 

We can use the Bitwise OR (|) operator to combine these flags into a single "characteristics" variable.

if (animal == "sheep")   characteristics = kHasTeeth | kHasHair | kHasLungs; else if (animal == "snake")     characteristics = kHasScales | kHasLungs; else if (animal == "goldfish")     characteristics = kHasScales | kHasGills; else if (animal == "shark")     characteristics = kHasTeeth | kHasScales | kHasGills; else if (animal == "elephant")     characteristics = kHasTusks | kHasLungs | kHasHair; 

We can use the Bitwise AND (&) variable to test if a particular flag is turned on.

if ( (characteristics & kHasTeeth) )    message = "This animal has teeth."; 

Here's a more complex example:

if ( (characteristics & kHasScales) && (characteristics & kHasLungs) )    message = "This animal is probably a reptile."; else if ( (characteristics & kHasScales) && (characteristics & kHasGills) )    message = "This animal is probably a fish."; 

The Bitwise Negation (~) operator give you the opposite bit pattern of it's operand, typically extended up to 32 bits.

X = 1      // x = 00000000000000000000000000000001 X = ~X;    // x = 11111111111111111111111111111110 

This operator is commonly combined with the Bitwise AND (&) operator to clear individual bits from flags. For example, the following code turns off the kHasHair bit in characteristics.

characteristics = (characteristics & ~kHasHair); 

This can be shortened to

characteristics &= ~kHasHair; 

Note that this code will turn the kHasHair bit off, if it is on, and will have no effect otherwise. If you want to TOGGLE the value of that bit, use the XOR (^) operator, without the negation.

characteristics ^= kHasHair; 

More on XOR below...

^ XOR

The bitwise XOR operator is one of my favorites, since it often lies at the center of some interesting arcane trickery.

The effect of XOR

A = A ^ B 

or

A ^= B 

Is to toggle any bits in A which are set (or turned on) in B. If those bits are turned off in A, they are turned on. If they are turned on in A, they are turned off.

Interestingly, if you apply it twice, you get the same result back. For example, if you execute the following code

myVar = (myVar ^ X) ^ X 

or

myVar ^= X myVar ^= X 

Where X is any integer value, then the value of myVar is unchanged.

As described above, the toggle nature of XOR makes it ideal for toggling flags.

myFlags = (myFlags ^ SomeFlag); 

or

myFlags ^= SomeFlag; 

A more obscure use of XOR I've used is to swap the values of two integer variables, without requiring a third temporary variable. Normally, if you wanted to swap two integer variables, you'd do this:

var temp = x; x = y; y = temp; 

However, back in the days when I cared about such things as minimizing the numbers of registers, I would write code like this:

x ^= y; y ^= x; x ^= y; 

..which had the same effect. Let's examine what is going on with some real values to get an intuitive understanding of why. Let's say X is equal to 6 and Y is equal to 5. The following tables shows what is happening in binary.

                      X               Y original values       110             101 x ^= y                011             101   x=x^y y ^= x                011             110   y=y^(x^y) or y=x x ^= y                101             110   x=(x^y)^x or x=y 

voila! they've been swapped!

XOR is often used in simple (and easily crackable) encryption algorithms, since you can apply it to a series of character codes to first encrypt, and then decrypt them.

<< Shift Left >> Shift Right

The shift left operator shift all the bits to the left in a number. For example:

x = 6                   // X is 110 in binary x = (x << 1)            // X is now 1100 in binary, or 12 in decimal. 

Notice that shifting a number to the left by 1 is the same as multiplying it by two. Shifting to the left by N bits is the same as multiplying it by 2 to the N. Similarly, the shift right operator is the same as integer-dividing by 2 to the N.

Back when CPU speed was a major issue, you could get speed gains by substituting left and right shifts for multiplies and divides in this manner. However, in high level languages like Javascript and Actionscript, there is no real savings.

I do often use the shift operator to convert ordinal numbers to flags. For example, in my Sudoku software, I use a single number to indicate which digits (from 1-9) are possibilities for a particular cell.

I can set a digit as a possibilty using code like the following:

possibles = (possibles | (1 << digit)); 

or

possibles |= (1 << digit); 

and I can clear a digit as a possibility using code like this:

possibles = (possibles & ~(1 << digit)); 

or

possibles &= ~(1 << digit); 

If there are 9 possible digits (1-9), I can set all the possible digits at once, using this:

N = 9 possibles = (1 << N)-1; 

Note however, that this code assumes I am using bit-numbers 0 thru N-1, rather than bit-numbers 1 thru N. As an old-school programmer, I pretty much always use zero-based counting systems, when I can, since it simplifies the resulting code.

Another very common way I use the shift and bitwise logic operators is for converting individual R,G and B values into colors.

compositeColor = (red << 16) | (green << 8) | blue; 

--
Siva
9886179349