Bitwise Practice

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`

# Bitvectors

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` .

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! Source: cowbirdsinlove.com