Bit Math Tutorial 226z20

Bit Math Tutorial

by CosineKitty

Note: This page was inspired by a conversation that took place in the Arduino forum.

Table of Contents 

Introduction



The Binary System



Bitwise AND



Bitwise OR



Bitwise XOR



Bitwise NOT



Bit Shift Operators



A word of caution: bitwise operators vs. boolean operators



Putting it all together: common problems solved

o

A word about port s in the Atmega8 microcontroller

o

More advanced example: disabling an interrupt

o

Saving memory by packing multiple data items in a single byte



Quick Reference

Introduction Often when programming in the Arduino environment (or on any computer, for that matter), the ability to manipulate individual bits will become useful or even necessary. Here are some situations where bit math can be helpful: 

Saving memory by packing up to 8 true/false data values in a single byte.



Turning on/off individual bits in a control or hardware port .



Performing certain arithmetic operations involving multiplying or dividing by powers of 2. In this tutorial, we first explore the basic bitwise operators available in the C++ language. Then we learn how to combine them to perform certain common useful operations.

The Binary System To better explain the bitwise operators, this tutorial will express most integer values using binary notation, also known as base two. In this system, all integer values use only the values 0 and 1 for

each digit. This is how virtually all modern computers store data internally. Each 0 or 1 digit is called a bit, short for binary digit. In the familiar decimal system (base ten), a number like 572 means 5*102 + 7*101 + 2*100. Likewise, in binary a number like 11010 means 1*24 + 1*23 + 0*22 + 1*21 + 0*20 = 16 + 8 + 2 = 26. It is crucial that you understand how the binary system works in order to follow the remainder of this tutorial. If you need help in this area, one good place to start is the Wikipedia article on the binary system. Unfortunately, most C++ compilers do not have any means of expressing binary numbers directly in source code. A few allow the prefix 0b followed by a series of 0 and 1 digits, e.g. 0b11 == 3. The C++ compiler used by Arduino does not this syntax. However, starting in Arduino 0007, the constants B0through B11111111 are defined for your convenience.

Bitwise AND The bitwise AND operator in C++ is a single ampersand, &, used between two other integer expressions. Bitwise AND operates on each bit position of the surrounding expressions independently, according to this rule: if both input bits are 1, the resulting output is 1, otherwise the output is 0. Another way of expressing this is: 0 0 1 1

& & & &

0 1 0 1

== == == ==

0 0 0 1

In Arduino, the type int is a 16-bit value, so using & between two intexpressions causes 16 simultaneous AND operations to occur. In a code fragment like: int a = 92; int b = 101; int c = a & b;

// in binary: 0000000001011100 // in binary: 0000000001100101 // result: 0000000001000100, or 68 in decimal.

Each of the 16 bits in a and b are processed by using the bitwise AND, and all 16 resulting bits are stored in c, resulting in the value 01000100 in binary, which is 68 in decimal. One of the most common uses of bitwise AND is to select a particular bit (or bits) from an integer value, often called masking. For example, if you wanted to access the least significant bit in a variable x, and store the bit in another variable y, you could use the following code: int int x = y =

x = 5; y = x & 1; 4; x & 1;

// // // //

binary: 101 now y == 1 binary: 100 now y == 0

Bitwise OR The bitwise OR operator in C++ is the vertical bar symbol, |. Like the &operator, | operates independently each bit in its two surrounding integer expressions, but what it does is different (of

course). The bitwise OR of two bits is 1 if either or both of the input bits is 1, otherwise it is 0. In other words: 0 0 1 1

| | | |

0 1 0 1

== == == ==

0 1 1 1

Here is an example of the bitwise OR used in a snippet of C++ code: int a = 92; int b = 101; int c = a | b;

// in binary: 0000000001011100 // in binary: 0000000001100101 // result: 0000000001111101, or 125 in decimal.

Bitwise OR is often used to make sure that a given bit is turned on (set to 1) in a given expression. For example, to copy the bits from a into b, while making sure the lowest bit is set to 1, use the following code: b = a | 1;

Bitwise XOR There is a somewhat unusual operator in C++ called bitwise exclusive OR, also known as bitwise XOR. (In English this is usually pronounced "eks-or".) The bitwise XOR operator is written using the caret symbol ^. This operator is very similar to the bitwise OR operator |, only it evaluates to 0 for a given bit position when both of the input bits for that position are 1: 0 0 1 1

^ ^ ^ ^

0 1 0 1

== == == ==

0 1 1 0

Another way to look at bitwise XOR is that each bit in the result is a 1 if the input bits are different, or 0 if they are the same. Here is a simple code example: int x = 12; int y = 10; int z = x ^ y;

// binary: 1100 // binary: 1010 // binary: 0110, or decimal 6

The ^ operator is often used to toggle (i.e. change from 0 to 1, or 1 to 0) some of the bits in an integer expression while leaving others alone. For example: y = x ^ 1;

// toggle the lowest bit in x, and store the result in y.

Bitwise NOT The bitwise NOT operator in C++ is the tilde character ~. Unlike & and |, the bitwise NOT operator is applied to a single operand to its right. Bitwise NOT changes each bit to its opposite: 0 becomes 1, and 1 becomes 0. For example: int a = 103; int b = ~a;

// binary: // binary:

0000000001100111 1111111110011000 = -104

You might be surprised to see a negative number like -104 as the result of this operation. This is because the highest bit in an int variable is the so-called sign bit. If the highest bit is 1, the

number is interpreted as negative. This encoding of positive and negative numbers is referred to as two's complement. For more information, see the Wikipedia article on two's complement. As an aside, it is interesting to note that for any integer x, ~x is the same as-x-1. At times, the sign bit in a signed integer expression can cause some unwanted surprises, as we shall see later.

Bit Shift Operators There are two bit shift operators in C++: the left shift operator << and the right shift operator >>. These operators cause the bits in the left operand to be shifted left or right by the number of positions specified by the right operand. For example: int int int started

a = 5; b = a << 3; c = b >> 3; with

// binary: 0000000000000101 // binary: 0000000000101000, or 40 in decimal // binary: 0000000000000101, or back to 5 like we

When you shift a value x by y bits (x << y), the leftmost y bits in x are lost, literally shifted out of existence: int a = 5; int b = a << 14; discarded

// binary: 0000000000000101 // binary: 0100000000000000 - the first 1 in 101 was

If you are certain that none of the ones in a value are being shifted into oblivion, a simple way to think of the left-shift operator is that it multiplies the left operand by 2 raised to the right operand power. For example, to generate powers of 2, the following expressions can be employed: 1 << 0 1 << 1 1 << 2 1 << 3 ... 1 << 8 1 << 9 1 << 10 ...

== == == ==

1 2 4 8

== 256 == 512 == 1024

When you shift x right by y bits (x >> y), and the highest bit in x is a 1, the behavior depends on the exact data type of x. If x is of type int, the highest bit is the sign bit, determining whether x is negative or not, as we have discussed above. In that case, the sign bit is copied into lower bits, for esoteric historical reasons: int x = -16; int y = x >> 3;

// binary: 1111111111110000 // binary: 1111111111111110

This behavior, called sign extension, is often not the behavior you want. Instead, you may wish zeros to be shifted in from the left. It turns out that the right shift rules are different for unsigned int expressions, so you can use a typecast to suppress ones being copied from the left: int x = -16; int y = unsigned(x) >> 3;

// binary: 1111111111110000 // binary: 0001111111111110

If you are careful to avoid sign extension, you can use the right-shift operator>> as a way to divide by powers of 2. For example: int x = 1000; int y = x >> 3;

// integer division of 1000 by 8, causing y = 125.

Assignment Operators Often in programming, you want to operate on the value of a variable x and store the modified value back into x. In most programming languages, for example, you can increase the value of a variable x by 7 using the following code: x = x + 7;

// increase x by 7

Because this kind of thing occurs so frequently in programming, C++ provides a shorthand notation in the form of specialized assignment operators. The above code fragment can be written more concisely as: x += 7;

// increase x by 7

It turns out that bitwise AND, bitwise OR, left shift, and right shift, all have shorthand assignment operators. Here is an example: int x = 1; x <<= 3; x |= 3; x &= 1; x ^= 4; x ^= 4;

// // // // // //

binary: binary: binary: binary: binary: binary:

0000000000000001 0000000000001000 0000000000001011 - because 3 is 11 in binary 0000000000000001 0000000000000101 - toggle using binary mask 100 0000000000000001 - toggle with mask 100 again

There is no shorthand assignment operator for the bitwise NOT operator ~; if you want to toggle all the bits in x, you need to do this: x = ~x;

// toggle all bits in x and store back in x

A word of caution: bitwise operators vs. boolean operators It is very easy to confuse the bitwise operators in C++ with the boolean operators. For instance, the bitwise AND operator & is not the same as the boolean AND operator &&, for two reasons: 

They don't calculate numbers the same way. Bitwise & operates independently on each bit in its operands, whereas && converts both of its operands to a boolean value (true==1 or false==0), then returns either a single true or false value. For example, 4 & 2 == 0, because 4 is 100 in binary and 2 is 010 in binary, and none of the bits are 1 in both integers. However, 4 && 2 == true, and true numerically is equal to 1. This is because 4 is not 0, and 2 is not 0, so both are

considered as boolean truevalues. 

Bitwise operators always evaluate both of their operands, whereas boolean operators use socalled short-cut evaluation. This matters only if the operands have side-effects, such as causing output to occur or modifying the value of something else in memory. Here is an example of how two similar looking lines of code can have very different behavior:

int fred (int x) { Serial.print ("fred "); Serial.println (x, DEC); return x; } void setup() { Serial.begin (9600); } void loop() { delay(1000); // wait 1 second, so output is not flooded with serial data! int x = fred(0) & fred(1); }

If you compile and this program, and then monitor the serial output from the Arduino GUI, you will see the following lines of text repeated every second: fred 0 fred 1

This is because both fred(0) and fred(1) are called, resulting in the generated output, the return values 0 and 1 are bitwise-ANDed together, storing 0 in x. If you edit the line int x = fred(0) & fred(1);

and replace the bitwise & with its boolean counterpart &&, int x = fred(0) && fred(1);

and compile, , and run the program again, you may be surprised to see only a single line of text repeated every second in the serial monitor window: fred 0

Why does this happen? This is because boolean && is using a short-cut: if its left operand is zero (a.k.a. false), it is already certain that the result of the expression will be false, so there is no need to evaluate the right operand. In other words, the line of code int x = fred(0) && fred(1); is identical in meaning to: int x; if (fred(0) == 0) { x = false; // stores 0 in x } else { if (fred(1) == 0) { x = false; // stores 0 in x } else { x = true; // stores 1 in x } }

Clearly, the boolean && is a lot more concise way to express this surprisingly complex piece of logic. As with bitwise AND and boolean AND, there are differences between bitwise OR and boolean OR. The bitwise OR operator | always evaluates both of its operands, whereas the boolean OR operator || evaluates its right operand only if its left operand is false (zero). Also, bitwise | operates independently on all of the bits in its operands, whereas boolean || treats both of its operands as either true (nonzero) or false (zero), and evaluates to either true (if either operand is nonzero) or false (if both operands are zero).

Putting it all together: common problems solved Now we start exploring how we can combine the various bitwise operators to perform useful tasks using C++ syntax in the Arduino environment. A word about port s in the Atmega8 microcontroller Usually when you want to read or write to digital pins in the Atmega8, you use the built-in functions digitalRead() or digitalWrite() supplied by the Arduino environment. Suppose that in your setup() function, you wanted to define the digital pins 2 through 13 as output, and then you wanted pins 11, 12, and 13 to be set HIGH, and all the other pins set LOW. Here is how one would typically accomplish this: void setup() { int pin; for (pin=2; pin <= 13; ++pin) { pinMode (pin, OUTPUT); } for (pin=2; pin <= 10; ++pin) { digitalWrite (pin, LOW); } for (pin=11; pin <= 13; ++pin) { digitalWrite (pin, HIGH); } }

It turns out there is a way to accomplish the same thing using direct access to Atmega8 hardware ports and bitwise operators: void setup() { // set pins 1 (serial transmit) and 2..7 as output, // but leave pin 0 (serial receive) as input // (otherwise serial port will stop working!) ... DDRD = B11111110; // digital pins 7,6,5,4,3,2,1,0 // set pins 8..13 as output... DDRB = B00111111; // digital pins -,-,13,12,11,10,9,8 // Turn off digital output pins 2..7 ... PORTD &= B00000011; // turns off 2..7, but leaves pins 0 and 1 alone // Write simultaneously to pins 8..13... PORTB = B00111000; // turns on 13,12,11; turns off 10,9,8 }

This code takes advantage of the fact that the control s DDRD and DDRBeach contain 8 bits that determine whether a given digital pin is output (1) or input (0). The upper 2 bits in DDRB are not used, because there is no such thing is digital pin 14 or 15 on the Atmega8. Likewise, the port s PORTBand PORTD contain one bit for the most recently written value to each digital pin, HIGH (1) or LOW (0). Generally speaking, doing this sort of thing is not a good idea. Why not? Here are a few reasons: 

The code is much more difficult for you to debug and maintain, and is a lot harder for other people to understand. It only takes a few microseconds for the processor to execute code, but it

might take hours for you to figure out why it isn't working right and fix it! Your time is valuable, right? But the computer's time is very cheap, measured in the cost of the electricity you feed it. Usually it is much better to write code the most obvious way. 

The code is less portable. If you use digitalRead() and digitalWrite(), it is much easier to write code that will run on all of the Atmel microcontrollers, whereas the control and port s can be different on each kind of microcontroller.



It is a lot easier to cause unintentional malfunctions with direct port access. Notice how the line DDRD = B11111110; above mentions that it must leave pin 0 as an input pin. Pin 0 is the receive line on the serial port. It would be very easy to accidentally cause your serial port to stop working by changing pin 0 into an output pin! Now that would be very confusing when you suddenly are unable to receive serial data, wouldn't it? So you might be saying to yourself, great, why would I ever want to use this stuff then? Here are some of the positive aspects of direct port access:



If you are running low on program memory, you can use these tricks to make your code smaller. It requires a lot fewer bytes of compiled code to simultaneously write a bunch of hardware pins simultaneously via the port s than it would using a for loop to set each pin separately. In some cases, this might make the difference between your program fitting in flash memory or not!



Sometimes you might need to set multiple output pins at exactly the same time. Calling digitalWrite(10,HIGH); followed bydigitalWrite(11,HIGH); will cause pin 10 to go HIGH several microseconds before pin 11, which may confuse certain time-sensitive external digital circuits you have hooked up. Alternatively, you could set both pins high at exactly the same moment in time using PORTB |= B1100;



You may need to be able to turn pins on and off very quickly, meaning within fractions of a microsecond. If you look at the source code inlib/targets/arduino/wiring.c, you will see that digitalRead() and digitalWrite() are each about a dozen or so lines of code, which get compiled into quite a few machine instructions. Each machine instruction requires one clock cycle at 16MHz, which can add up in time-sensitive applications. Direct port access can do the same job in a lot fewer clock cycles. More advanced example: disabling an interrupt Now let's take what we have learned and start to make sense of some of the weird things you will sometimes see advanced programmers do in their code. For example, what does it mean when someone does the following? // Disable the interrupt. GICR &= ~(1 << INT0);

This is an actual code sample from the Arduino 0007 runtime library, in the file lib\targets\arduino\winterrupts.c. First of all, we need to know what GICR and INT0 mean. It turns out that GICR is a control that defines whether certain U

interrupts are enabled (1) or disabled (0). If we search through the Arduino standard header files for INT0, we find various definitions. Depending on what kind of microcontroller you are writing for, you have either #define INT0

6

#define INT0

0

or So on some processors, the above line of code will compile to: GICR &= ~(1 << 0);

and on others, it will compile to: GICR &= ~(1 << 6);

Let us study the latter case, as it is more illustrative. First of all, the value(1 << 6) means that we shift 1 left by 6 bits, which is the same as 26, or 64. More useful in this context is to see this value in binary: 01000000. Then, the bitwise NOT operator ~ is applied to this value, resulting in all the bits being toggled: 10111111. Then the bitwise AND assignment operator is used, so the code above has the same effect as: GICR = GICR & B10111111;

This has the effect of leaving all the bits alone in GICR, except for the second-to-highest bit, which is turned off. In the case where INT0 has been defined to 0 for your particular microcontroller, the line of code would instead be interpreted as: GICR = GICR & B11111110;

which turns off the lowest bit in the GICR , but leaves the other bits as they were. This is an example of how the Arduino environment can a wide variety of microcontrollers with a single line of runtime library source code. Saving memory by packing multiple data items in a single byte There are many situations where you have a lot of data values, each of which can be either true or false. An example of this is if you are building your own LED grid and you want to display symbols on the grid by turning individualLEDs on or off. An example of a 5x7 bitmap for the letter X might look like this:

A simple way to store such an image is using an array of integers. The code for this approach might look like this: const prog_uint8_t BitMap[5][7] = { save RAM

// store in program memory to

{1,1,0,0,0,1,1}, {0,0,1,0,1,0,0}, {0,0,0,1,0,0,0}, {0,0,1,0,1,0,0}, {1,1,0,0,0,1,1} }; void DisplayBitMap() { for (byte x=0; x<5; ++x) { for (byte y=0; y<7; ++y) { byte data = pgm_read_byte (&BitMap[x][y]); from program memory if (data) { // turn on the LED at location (x,y) } else { // turn off the LED at location (x,y) } } } }

// fetch data

If this were the only bitmap you had in your program, this would be a simple and effective solution to the problem. We are using 1 byte of program memory (of which there are about 7K available in the Atmega8) for each pixel in our bitmap, for a total of 35 bytes. This is not so bad, but what if you wanted a bitmap for each of the 96 printable characters in the ASCII character set? This would consume 96*35 = 3360 bytes, which would leave a lot less flash memory for holding your program code. There is a much more efficient way to store a bitmap. Let us replace the 2-dimensional array above with a 1-dimensional array of bytes. Each byte contains 8 bits, and we will use the lowest 7 bits of each to represent the 7 pixels in a column of our 5x7 bitmap: const prog_uint8_t BitMap[5] = {

// store in program memory to save

RAM B1100011, B0010100, B0001000, B0010100, B1100011 };

(Here we are using the predefined binary constants available starting in Arduino 0007.) This allows us to use 5 bytes for each bitmap instead of 35. But how do we make use of this more compact data format? Here is the answer: we rewrite the function DisplayBitMap() to access the individual bits in each byte of the BitMap... void DisplayBitMap() { for (byte x=0; x<5; ++x) { byte data = pgm_read_byte (&BitMap[x]); // fetch data from program memory for (byte y=0; y<7; ++y) { if (data & (1<
}

The crucial line to understand is if (data & (1<
The expression (1<
Quick Reference In this quick reference, we refer to the bits in a 16-bit integer starting with the least significant bit as bit 0, and the most significant bit (the sign bit if the integer is signed) as bit 15, as illustrated in this diagram:

Whenever you see the variable n, its value is assumed to be 0 through 15. y = (x >> n) & 1; 0 or 1. x &= ~(1 << n); left alone. x &= (1<<(n+1))-1; bits set to 0. x |= (1 << n); left alone. x ^= (1 << n); alone. x = ~x;

// n=0..15.

stores nth bit of x in y.

// forces nth bit of x to be 0.

y becomes

all other bits

// leaves alone the lowest n bits of x; all higher // forces nth bit of x to be 1. // toggles nth bit of x.

all other bits

all other bits left

// toggles ALL the bits in x.

Here is an interesting function that uses both bitwise & and boolean &&. It returns true if and only if the given 32-bit integer x is a perfect power of 2, i.e., 1, 2, 4, 8, 16, 32, 64, etc. For example, calling IsPowerOfTwo(64) will returntrue, but IsPowerOfTwo(65) returns false. To see how this function works, let us use the number 64 as an example of a power of 2. In binary, 64 is 1000000. When we subtract 1 from 1000000, we get 0111111. Applying bitwise &, the result is 0000000. But if we do the same with 65 (binary 1000001), we get1000001 & 1000000 == 1000000, which is not zero. bool IsPowerOfTwo (long x) { return (x > 0) && (x & (x-1) == 0); }

Here is a function that counts how many bits in the 16-bit integer x are 1 and returns the count: int CountSetBits (int x) { int count = 0; for (int n=0; n<16; ++n) { if (x & (1<
} return count; }

Another way is this: int CountSetBits (int x) { unsigned int count; for (count = 0; x; count++) x &= x - 1; return count; }