Understanding the bitwise AND Operator

Question

I have been reading about bit operators in Objective-C in Kochan's book, "Programming in Objective-C".

I am VERY confused about this part, although I have really understood most everything else presented to me thus far.

Here is a quote from the book:

The Bitwise AND Operator

Bitwise ANDing is frequently used for masking operations. That is, this operator can be used easily to set specific bits of a data item to 0. For example, the statement

w3 = w1 & 3;

assigns to w3 the value of w1 bitwise ANDed with the constant 3. This has the same ffect of setting all the bits in w, other than the rightmost two bits to 0 and preserving the rightmost two bits from w1.

As with all binary arithmetic operators in C, the binary bit operators can also be used as assignment operators by adding an equal sign. The statement

word &= 15;

therefore performs the same function as the following:

word = word & 15;

Additionally, it has the effect of setting all but the rightmost four bits of word to 0. When using constants in performing bitwise operations, it is usually more convenient to express the constants in either octal or hexadecimal notation.

OK, so that is what I'm trying to understand. Now, I'm extremely confused with pretty much this entire concept and I am just looking for a little clarification if anyone is willing to help me out on that.

When the book references "setting all the bits" now, all of the bits.. What exactly is a bit. Isn't that just a 0 or 1 in 2nd base, in other words, binary?

If so, why, in the first example, are all of the bits except the "rightmost 2" to 0? Is it 2 because it's 3 - 1, taking 3 from our constant?

Thanks!

Answer 1

Numbers can be expressed in binary like this:

3    = 000011
5    = 000101
10   = 001010

...etc. I'm going to assume you're familiar with binary.

Bitwise AND means to take two numbers, line them up on top of each other, and create a new number that has a 1 where both numbers have a 1 (everything else is 0).

For example:

    3          =>  00011
  & 5          =>  00101
------           -------
    1              00001

Bitwise OR means to take two numbers, line them up on top of each other, and create a new number that has a 1 where either number has a 1 (everything else is 0).

For example:

    3          =>  00011
  | 5          =>  00101
------           -------
    7              00111

Bitwise XOR (exclusive OR) means to take two numbers, line them up on top of each other, and create a new number that has a 1 where either number has a 1 AND the other number has a 0 (everything else is 0).

For example:

    3          =>  00011
  ^ 5          =>  00101
------           -------
    6              00110  

Bitwise NOR (Not OR) means to take the Bitwise OR of two numbers, and then reverse everything (where there was a 0, there's now a 1, where there was a 1, there's now a 0).

Bitwise NAND (Not AND) means to take the Bitwise AND of two numbers, and then reverse everything (where there was a 0, there's now a 1, where there was a 1, there's now a 0).

Continuing: why does word &= 15 set all but the 4 rightmost bits to 0? You should be able to figure it out now...

     n          =>  abcdefghjikl
  & 15          =>  000000001111
------            --------------
     ?              00000000jikl

(0 AND a = 0, 0 AND b = 0, ... j AND 1 = j, i AND 1 = i, ...)

How is this useful? In many languages, we use things called "bitmasks". A bitmask is essentially a number that represents a whole bunch of smaller numbers combined together. We can combine numbers together using OR, and pull them apart using AND. For example:

int MagicMap = 1;
int MagicWand = 2;
int MagicHat = 4;

If I only have the map and the hat, I can express that as myInventoryBitmask = (MagicMap | MagicHat) and the result is my bitmask. If I don't have anything, then my bitmask is 0. If I want to see if I have my wand, then I can do:

int hasWand = (myInventoryBitmask & MagicWand);
if (hasWand > 0) {
  printf("I have a wand\n");
} else {
  printf("I don't have a wand\n");
}

Get it?

EDIT: more stuff

You'll also come across the "bitshift" operator: << and >>. This just means "shift everything left n bits" or "shift everything right n bits".

In other words:

1 << 3 = 0001 << 3 = 0001000 = 8

And:

8 >> 2 = 01000 >> 2 = 010 = 2

Answer 2

"Bit" is short for "binary digit". And yes, it's a 0 or 1. There are almost always 8 in a byte, and they're written kinda like decimal numbers are -- with the most significant digit on the left, and the least significant on the right.

In your example, w1 & 3 masks everything but the two least significant (rightmost) digits because 3, in binary, is 00000011. (2 + 1) The AND operation returns 0 if either bit being ANDed is 0, so everything but the last two bits are automatically 0.

Answer 3

w1 =    ????...??ab
3  =    0000...0011
--------------------
&  =    0000...00ab

0 & any bit N = 0

1 & any bit N = N

So, anything bitwise anded with 3 has all their bits except the last two set to 0. The last two bits, a and b in this case, are preserved.

Answer 4

@cHao & all: No! Bits are not numbers. They’re not zero or one!

Well, 0 and 1 are possible and valid interpretations. Zero and one is the typical interpretation.

But a bit is only a thing, representing a simple alternative. It says “it is” or “it is not”. It doesn’t say anything about the thing, the „it“, itself. It doesn’t tell, what thing it is.

In most cases this won’t bother you. You can take them for numbers (or parts, digits, of numbers) as you (or the combination of programming languages, cpu and other hardware, you know as being “typical”) usaly do – and maybe you’ll never have trouble with them.

But there is no principal problem if you switch the meaning of “0“ and “1”. Ok, if doing this while programming assembler, you’ll find it a bit problematic as some mnemonics will do other logic then they tell you with their names, numbers will be negated and such things.

Have a look at http://webdocs.cs.ualberta.ca/~amaral/courses/329/webslides/Topic2-DeMorganLaws/sld017.htm if you want.

Greetings