Bitwise Practice

The practice problems below cover base conversion, bitwise operators, and constructing bitmasks. Reveal the answers for each section to double-check your work. Please ask questions about anything you don't understand!

A few miscellaneous notes about bit operations as you practice further:

  • operator precedence with bit operators and other operators can be tricky. Always use parentheses where precedence is ambiguous just to make sure operators execute in the order you expect. For instance, 1<<2 + 3<<4 means 1 << (2+3) << 4 due to precedence rules. Writing (1<<2) + (3<<4) ensures the correct order.
  • put a U after a number literal to make it unsigned. For instance, 1U means the literal 1 as an unsigned number.
  • put an L after a number literal to make it a long (64 bits) instead of an int, which it is by default. This highlights a common issue! If you want, for instance, a long with the index-32 bit on and everything else off, the following does not work:
long num = 1 << 32;

This is because the 1 is by default a signed int, and you cannot shift a signed int by 32 spaces because it has only 32 bits. Instead, you must specify that the literal be a long:

long num = 1L << 32;

With this material and the other material from the past lectures, test your understanding with the practice below.

Base Conversion

It is unwieldy to express any type larger than char in binary form, thus hex is an important friend to have. Mapping between base 16 and base 2 is straightforward and you should practice until it is second nature for you to see a hex value and visualize its binary equivalent and vice versa. (Converting between decimal and hex is less worthy of practice, and it is ok for it to be a chore in the isolated situations you have to convert manually.)

Practice hex to binary. The values are 32-bit unsigned integers. We did the first one for you!

Hex Binary
0x1 00000000 00000000 00000000 00000001
0x1ff 00000000 00000000 00000001 11111111
0x800000 00000000 10000000 00000000 00000000
0xa017 00000000 00000000 10100000 00010111

Practice binary to hex. The values are 32-bit unsigned integers.

Binary Hex
11111111 11111111 11111111 11111111 0xffffffff
00000010 00000000 10000000 00000000 0x2008000
00000000 00000000 00011111 11100000 0x1fe0
11111000 01111111 00000000 00000000 0xf87f0000

There is no need to memorize the entire ASCII table, but knowing the placement of a few key characters from which you can then find neighbors is worthwhile. Use man ascii to learn the codes for the three characters '0' 'A' 'a' and use them to do the following conversions.

Practice ascii to hex. The values are char.

Ascii Hex
'I' 0x49
'5' 0x35
'd' 0x64

What is the bitwise relationship between the placement of the lowercase and uppercase alphabet within the ASCII table?

Each lowercase letter is 32 + uppercase equivalent. This means simply flipping the bit at position 5 (counting from least significant bit at position 0) inverts the case of a letter.

You should also know the bit patterns for various distinctive unsigned and signed values.

What is the bit pattern for each of these constants?

Value Binary
-1 11111111 11111111 11111111 11111111
INT_MAX 01111111 11111111 11111111 11111111
INT_MIN 10000000 00000000 00000000 00000000
UINT_MAX 11111111 11111111 11111111 11111111

Unix Tools: gdb

Once you are comfortable with manual bit calculations, it's good to also learn how to use the Unix tools to do these calculations for you. The best tool to use for conversions is the debugger gdb. If you run it (even without a program to debug), you can use it as sort of a converter. The gdb print command (shortened p) defaults to decimal format. Use p/format to instead select other formats such as x for hex, t for binary, and c for char. Also check out the guide to GDB for more information about gdb.

$ gdb
(gdb) p 68
$1 = 68
(gdb) p/x 68
$2 = 44
(gdb) p/c 68
$3 = 'D'
(gdb) p/t 68
$4 = 1000100
(gdb) p 45 << 1        Note: can also print expressions, not just constants
$5 = 90

Another fun and handy tool to play with is this online visualizer for bitwise expressions written by Max Drach, a previous 107 CA. Check it out!

Bitwise Operators

You should know the behavior of all six bitwise operators in C: & | ~ ^ << >>.

Test your understanding of bitwise ops by evaluating the following expressions. (We used char to keep things simple, but the bitwise operators have same behavior for int, just more bits.)

Expression Evaluates to
unsigned char this, that, result;
this = 0xf0 11110000
that = 0x55 01010101
result = this & that 01010000 = 0x50
result = this | that 11110101 = 0xf5
result = this ^ that 10100101 = 0xa5
result = ~this 00001111 = 0x0f
result = this >> 2 00111100 = 0x3c
result = that << 1 10101010 = 0xaa


A bitvector is an unsigned value treated as a set of independent booleans. The bit at a given position represents a particular member and if that bit is on in the bitvector, the set contains that member. Changing a particular bit allows you to add or remove a member from the set. When operating on a bitvector, you apply a bitwise operator with a mask to isolate the bits of interest.

Bitwise operators are used to test, set, and clear individual bits and perform simple set operations. These are classic bitwise code idioms worth knowing!

Do you know how to perform operations on a bitvector? Test yourself with the expressions below. Assume mine and yours are unsigned ints. The terms "low" and "high" refer to "less significant" and "more significant", i.e. the lowest bit is the least significant. You will also see "rightmost" and "leftmost" used as synonyms for least and most significant.

How can you C expression
test if mine has lowest bit on (mine & 1) != 0
set lowest bit in yours yours = yours | 1
clear lowest bit in yours yours = yours & ~1
toggle lowest bit in yours yours = yours ^ 1
union mine with yours mine = mine | yours
intersect mine with yours mine = mine & yours
remove yours from mine mine = mine & ~yours

Other equivalent expressions are also valid answers. As an example, yours ^= 1 is equivalent to yours = yours ^ 1 .

Using and Constructing Bitmasks

When accessing an individual bit, a mask is used to isolate the bit of interest, e.g., 1 is the mask being used to test the least significant bit (mine & 1). Changing the mask changes which bit(s) is being operated on. For example, (mine & 2) tests the second least significant bit. Including other bits into the mask allows you to affect an entire group of bits, e.g., mine ^= 0x7 to toggle the 3 lowest bits.

Assume mine is an unsigned int being used as bitvector. For each listed task, show how to express it in C.

How can you C expression
test if mine has either of two lowest bits on (mine & 0x3) != 0
test if mine has both of two lowest bits on (mine & 0x3) == 0x3
set lowest 8 bits of mine mine |= 0xff
clear every other bit in mine mine &= 0x55555555 or
  mine &= 0xaaaaaaaa

For the last expression, using 0x55 as mask clears bits in position 1/3/5/etc. whereas using 0xaa as mask clears bits in position 0/2/4/6, etc.

A constant mask should always be expressed in hex (few of us are good at visualizing binary from decimal, but hex to binary is a snap), the exception being small decimal integer constants (0, 1,...). For a complex mask, it is pleasing to express the mask by its construction, as opposed to hard-coding a magic number. You should practice with building up masks by construction. You should also define constants (#define <CONSTANT> <VALUE> near the top of your file) where appropriate.

Give a C expression to construct each of the following masks for a 32-bit unsigned integer. When identifying bits by position, we count starting from the least significant bit at position 0.

Construct mask that has C expression
all bits on ~0 or -1
one bit on in position n, all others off 1 << n
n least significant bits on, all others off (1 << n) - 1
most significant bit on, all others off (1 << 31)
k most significant bits on, all others off (~0 << (32 - k)) or
  ~(~0U >> k)

Other equivalent expressions are also valid answers. 'U' suffix on integer constant indicates unsigned.

Bitwise Manipulation

Lastly, we present some slightly fancier bitwise manipulations. These constructions can be tricky to reason about at first, but working through them confirms you have solid understanding of the bitwise operators and the relationship to the two's complement representation.

Assume x and y are 32-bit signed ints and that right-shift performs an arithmetic (not logical) shift. For each listed expression, work out what result it produces.

Expression What result does it produce?
1 << x 2 to the power x
~x + 1 -x, arithmetic negation
x >> 31 -1 if x is negative, 0 otherwise
x &= (x - 1) clears lowest "on" bit in x
(x ^ y) < 0 true if x and y have opposite signs

In addition to trying these on paper, now would be a good time to fire up gdb and observe these operations in action!

Questions about any of these? Post on the discussion forum or come by helper hours!