Book 15: Twiddling Some Bits

Previous | Next

The following is a little mathematical, but once you start working with the MacOS commands for creating graphical user interfaces, you will need what you learn here. Don’t worry if you don’t understand everything in here, at the end of this chapter, I will give you a short little ‘cheat sheet’ on how you can use what is here in the most common case.

Bits and Numbers

One switch as a number of 1 or 0

As you may remember from Chapter 6, a computer is really only a collection of switches. A switch can be on or off. To express a number with a bunch of switches, you have to employ a trick:

The first switch gets two numbers assigned: 0 for off, 1 for on. If you want to express a higher number, you add an additional switch. When this second switch is 0, you only read the first switch, when it is 1, you add one more than the highest value that you can express with one switch to your number.

Various numbers as switches
 
Various numbers as switches

So, since a single switch can be 0 or 1, if the second switch is on, you add 2. So, with two switches, you can express the numbers from 0 through 3. If you count the 0, that’s four different states, twice as much as a single switch. And of course, you can add additional switches. When you add a third switch, turning it on adds one more than the highest number of the two previous switches, so that would be 3 + 1, or 4, giving you 8 different numbers, from 0 through 7.

This is actually how regular numbers work, too. You can express the numbers from 0 through 9 with each digit, ten different states. The second digit would thus be 10, and with two digits you can express numbers from 0 through 99, and the third digit would add 100.

And you can even use more symbols to express numbers, for example you can use 16 different symbols (0-9 and then the character a-f for example), and then two digits could express a number from 0 through 255.

To tell apart these different numbering systems, they are expressed as having a particular base. I.e. regular numbers are base 10, the switches above are base 2, the one I mentioned above is base 16 etc. Sometimes people also use Latin words to express this, with decimal for base 10, binary for base 2, hexa-decimal for base 16, octal for base 8.

Why would I care?

Well, sometimes, you need a whole bunch of switches. So, what you can do is take advantage of the fact that, under the hood, all numbers can be expressed as switches.

As of this writing, an int on the Mac uses at least 32 bits to store its number. That’s 32 switches you can cram efficiently into one parameter. Also, you don’t have to use all of them at once; if you need two switches, you can use two switches in an int, and if you later decide you need to pass additional switches to the function, you can use one of the unused 30 ones. You won’t always need this, but it can be handy when providing functions to other people who don’t want to rewrite all the spots where they’re using your code to add another boolean.

Bitwise Operators

Since this is so terribly convenient, C actually has a bunch of special operators to work with bits (which is what these switches are called in geek-speak). But most computers deal in batches of 8, 16 or 32 bits at all times. So, if you want to get a single bit (like a boolean, i.e. true or false) they will actually fetch more bits. So, all these bitwise operators operate on ints, and you simply specify which bit you want.

To specify a bit, you simply use a number where all bits are 0, except that one bit that you want. So, if you want to work on the second switch, which adds 2, that means you simply give it the number 2, because that is what number you would get when you set all other switches to 0. You can even set several bits, but of course then you’d only get 0 if none of these bits are 1. Since all the bits that you set to 0 are gone after the operation, hidden away, they are said to be masked out and this number for specifying a bit to operate on is called a bit mask.

There are six bitwise operators available for you, and they are called bitwise and, bitwise or, bitwise exclusive or, complement, bit-shift left and bit-shift right:

Bitwise And

This is the & operator. Yes, that’s a single ampersand, whereas the regulat logical and we already encountered used two. Watch out for typos here. It is an operator that goes between two values, different from the address-of operator that we also encountered before, which goes in front of a single one.

What it does is look at the two numbers, and compare each bit in the first number with the corresponding bit in the second number. If both are 1, the corresponsing bit in the result operation will also be 1. Otherwise, it will be 0. So, imagine we had three-bit numbers a = 101 and b = 011, which would be 5 and 3. We bitwise-and them together:

unsigned int myNum = 5 & 3;

What the computer now does is look at the rightmost digit, which is 1 in a and in b, so it will set the rightmost bit of myNum to 1. Then it will look at the next bit to the left, which is 0 in a and 1 in b. Since a is 0, bit 2 of myNum will be set to 0, too. The third bit of b is 0, so again, we’ll put a 0 in myNum‘s third digit from the right as well. So, the result of this operation would be 001, or simply 1.

Now how can we use this for switches? Well, you can use this to determine the value of a single switch: Build a number where all bits are 0 (and thus will end up 0 after an bitwise and no matter what the other number’s values are), and the bit for the one switch you want to test is 1. If the switch is 0 in the other number, your number will come back 0. Otherwise, it will come back with that single bit set to 1. So when you test number b against 010, you will get 010 back, which is 2.

Bitwise Or

This useful operator uses a single pipe, |. It works similar to bitwise and, just that it sets the corresponding bit in the result to 1 whenever any of the numbers has that bit set, and to 0 otherwise. So if a = 101 and b = 110, the result will be 111. If a = 001 and b = 101, the result will be 101.

This is very useful if you want to turn on a switch. Take a number that has only the switch(es) set to 1 that you actually want to turn on, and the | operator will turn them on in the result.

Bitwise Exclusive Or

This operator uses the caret symbol ^. What it does is similar to our regular bitwise or, but it also sets the result bit to 0 when both bits are 1. It essentially operates as an exclusive either … or, as opposed to the inclusive or we had above: If either a’s nth bit is set, or b’s nth bit, but not both, give me a 1.

This operator is a neat tool if you want to change the value of a switch without bothering to check its original value. It’s also handy as a simple encryption scheme: If you apply the same number to another number twice, using exclusive or (or xor), you get the original number back. Now, this is by no means a secure encryption scheme, and very easy to decode, but for example if you want to prevent every nit with a text editor to just point a text editor at the game you wrote and see the various text messages that tell the story of your game, you can use xor to turn it into illegible gibberish.

Bit-shift

There are two operators that shift the bits in a number. They are << and >>. What they do is move every one and zero one digit to the right, cutting off the digit that ‘falls off’ and using zero for the spot where there’s no value anymore. I.e. if you have 0110 and you bitshift it left, you get 1100, and if you bitshift it right you get 0011. The number you specify is how many digits you want to shift by. So, if you wanted to shift 0110 (which is 6) down by two bits, you’d do

unsigned int     myNum = 6 >> 2;

which gives you 0001, or 1 in myNum.

The let shift operator is handy for generating a bit mask in the first place. You can simply take the number 1 (which is the rightmost bit activated) and then shift it once for every additional digit:

#define FLAG_ONE    (1 << 0)
#define FLAG_TWO    (1 << 1)
#define FLAG_THREE  (1 << 2)
. . .

The right shift operator, in combination with left shift, is also very handy to implement simple compression schemes: If you know your numbers in a file will never be bigger than 15, you could use only 4 bits for storing each number. Since your computer operates with a byte as the smallest quantity, that means you have to do some bit-shifting to stuff two numbers into one byte: Bit-shift one number up by 4 bytes, then OR it onto the zeroes in the upper half of the other number. To get it back, do the reverse, which is masking out both numbers so you have them separately again, then shift down the one you originally shifted up.

Complement

The complement operator is the only unary operator in the bunch. It simply reverses all the bits in a number. You use it like this:

unsigned int myNum = ~10;    // 10 is 1010

Now myNum is 11111111111111111111111111110101. All those ones are there because on a typical Mac, an int is 32 bits in length, so we have 28 zeroes to the left of the 1010 that I didn’t bother typing.

Variants of these Operators

As for most operators that have two operands, there are also versions of these operators that are fused with the = operator. They are &=, |=, ^=, <<= and >>=.

Finally…

Okay, here’s the cheat sheet:

    if( (myFlags & FLAG_ONE) == FLAG_ONE ) ...

Test if a certain bit is set.

    myFlags &= ~FLAG_ONE;

Clear a bit.

    myFlags |= FLAG_ONE;

Turn on a bit.

    #define FLAG_ONE    (1 << 0)
    #define FLAG_TWO    (1 << 1)

Declare constants with bit masks for naming your switches.

In case you were wondering, no, there is no way in standard C at this time to write a binary number in source code. You can write hexadecimal numbers by starting them with 0x, and octal numbers by starting them with a 0, but no way to write binary numbers yet.
Yes, you read that right. You do not want to write your numbers starting with a zero. They will turn out as different numbers, because 021 is not 21, it's 17.

Previous | Next

This entry was posted in C Tutorial. Bookmark the permalink.

One Response to Book 15: Twiddling Some Bits

  1. transforme says:

    “Bit-shift one number up by 4 bytes, then OR it onto the zeroes in the upper half of the other number. To get it back, do the reverse, which is masking out both numbers so you have them separately again, then shift down the one you originally shifted up.”

    Could you please give an example of what you means here ?

Leave a Reply

Your email address will not be published. Required fields are marked *


*