First we define bits, bit arrays and bit masks, relating these to data structures, addressable memory storage, registers and binary protocol frames.

Bitwise logic is introduced with simple practical examples – bitwise operators and bit shifts – setting individual bits on or off, extracting bits for reading, manipulating bits or checking bit field values.

In Assembler, C and other programming languages bit manipulation is common especially when implementing low level hardware interfaces, embedded microcontroller based devices, processing sensor, machine, network and peripheral data.

Graphics programming and image manipulation also utilises bitwise operations and bitmaps to perform animation (shifting and moving bits), compositing and pixel value modification.

### Bits, Bytes & Bitmasks Explained

Bits are smallest unit of storage representing either a binary 1 or 0.

A byte is a group of binary digits or bits (typically eight) operated on as a unit.

Bit fields are a series or array of bits in adjacent memory.

Bit values might represent a set of individual attributes (boolean on/off “flags” or status fields), a register value – storage address / instruction, or encapsulate binary encoded data.

A bitmask (or mask) is an ordered set of bits of defined length used in bitwise logic to set, invert or manipulate another bit field.

### Registers – Bit Arrays

Registers encapsulate a set of ordered bits in storage with a defined bit length typically expressed as power of base 2 (commonly 8 / 16 / 32 / 64 / 128 bit).

7 | 6 | 5 | 4 | 3 | 2 | 1 | 0 |

An 8 bit register can hold unsigned (positive) numbers from 0 to 255 or signed (includes negative) values from -128 to +127 (where bit 7 is a sign bit).

Registers are used to address memory locations for computations within central processing unit, configuration parameters or IO from data storage, ports, or peripherals.

### Bits in a Byte – Memory Address

Bitwise shifting operators, along with logical AND can be used to access individual bits within a byte of memory for any variable in C.

To read value of bit at index 4 of a variable x

int x = 16; // 10000 printf("%d\n", (x >> 4) & 0x01); // Prints 1

### Network Protocols – Binary Bit Sequences

Bit sequences are used in network protocols where packetised messages are arranged into frames containing fields with defined offset and length.

A frame refers to the entire data packet which is being sent/received during a communication. Each protocol defines a specification of its own frame format.

An RS232 serial protocol frame defines a bit sequence –

Frame: | Start | Data | Parity | Stop |

Size (bits): | 1 | 5-9 | 1 | 1-2 |

Bitwise operators and shifts can be used to efficiently read, set or modify fields within a network protocol packet.

### Bitwise Operators

Bitwise operations allow setting bit sequence values in a single operation and are more efficient than loops or maintaining individual bits.

Symbol | Operator |
---|---|

`&` | bitwise AND |

`|` | bitwise inclusive OR |

`^` | bitwise XOR (exclusive OR) |

`<<` | left shift |

`>>` | right shift |

`~` | bitwise NOT (one’s complement) (unary) |

Logical operators AND, OR, XOR (Exclusive OR) and NOT (Negation) implement bitwise manipulation, incurring a minimal number of processing instructions.

Comparing bit by bit –

- OR sets a bit if one or both operators are true: 1110 OR 0000 = 1110
- AND sets a bit if both operators are true: 1010 AND 1101 = 1000
- AND with zero-check tests if any bit is set: 1010 AND 0010 = 0010 ≠ 0
- XOR sets a bit if only one operator is true: 1010 XOR 0100 = 1110
- NOT inverts all bits: NOT 1011 = 0100

Bitwise operators work on integer and character data types and do not modify value of their arguments so assignment is typically used such as =, +=, -=, |=, &= for example x |= (y & z).

**Arithmetic Bit Shifts**

Bit or Arithmetic shift operators `<<`

`>>`

treat a value as a series of individual bits rather than a numerical quantity, shifting (or moving) bit positions left or right.

These operations are useful to move a bit or set of bits to a specific positional index.

In a left shift operation (`<<`

) bits are moved by one position to the left and last digit is zero filled. This is equivalent to multiplication of a signed integer by a power of 2.

0 | 1 | 1 | 0 | 1 | 0 | 1 | 1 |

Left shifting 2 bits ( `<< 2`

) results in

1 | 0 | 1 | 0 | 1 | 1 | 0 | 0 |

A right shift operation (`>>`

) moves bits right by a specified number of positions, dividing number by 2.

In more general form we can say –

// x multiplied by 2ⁿ x << n // x divided by 2ⁿ x >> N

Notes –

- Bits shifted from end are lost due to overflow, they do not wrap around.
- Right bitshift on signed types – gcc promises to always give the sane behavior (sign-bit-extension) but ISO C allows the implementation to zero-fill the upper bits.

### Defining bit masks in C

Bitmasks are used in bit manipulation and combined with a logical operator (`AND`

, `OR`

`XOR`

) define a pattern for bits to keep or discard.

In c++14 which supports binary literals bit masks are defined –

const uint8_t mask0 = 0b00000001 ; // represents bit 0 const uint8_t mask1 = 0b00000010 ; // represents bit 1 const uint8_t mask2 = 0b00000100 ; // represents bit 2 ...

Using Hexadecimal

const uint8_t mask0 = 0x01 ; // bit 0 0000 0001 const uint8_t mask1 = 0x02 ; // bit 1 0000 0010 const uint8_t mask2 = 0x03 ; // bit 2 0000 0100 ...

Or with bit shift operator

const uint8_t mask0 = 1 << 0 ; // 0000 0001 const uint8_t mask1 = 1 << 1 ; // 0000 0010 const uint8_t mask2 = 1 << 2 ; // 0000 0100 ...

### Set, Clear, Modify, Toggle & Check Bits

**Set a bit**

Set the nth bit ( zero up to n-1 ) of number

number |= 1UL << n

Set bit 0 of i to one

i |= 1 << 0; // Example 000 i 001 1 << 0; 001 i |= 1 << 0;

- the
`<<`

operator is left “bit shift” operator which moves all bits to the left n times. `1UL`

species numeric literal 1 with type`Unsigned Long`

**Clear a bit**

Set nth bit of number to zero

number &= ~(1UL << n);

Set bit 1 of i to zero

i &= ~(1UL << 1); // Example 010 i 000 ~(1UL << 1) 000 i &= ~(1UL << 1);

`~`

negates value of bit 1 from 1 to 0`AND`

evaulates false as both operands are not equal

**Toggle (flip) a bit**

Toggle nth bit of number

number ^= 1UL << n;

Toggle (flip) bit 0 of i

i ^= 1 << 0; // Example 001 i 001 1 << 0 000 i ^= 1 << 0

`^=`

represents`XOR`

exclusive OR with assignment, output is true when operand bits are different

**Check a bit is set**

True if nth bit of number equals 1

bit = (number >> n) & 1U;

Check bit 7 of i assign 1 or 0 to bit

int bit = (i >> 7) & 1U;

**Modify – Changing a bit to x (1 or 0)**

// 2s complement system with negation behaviour number ^= (-x ^ number) & (1UL << n); // portable number = (number & ~(1UL << n)) | (x << n);

Set bit 7 of i to x

i ^= (-x ^ i) & (1UL << 7); i = (i & ~(1UL << 7)) | (x << 7);

Notes –

- range / bounds checking is not applied, out of bounds shift index result in undefined behaviour
- Use
`1ULL`

if`number`

is wider than`unsigned long`

- endianess (position of most / least significant bit) and signing varies between platforms and compilers

### Bitwise Functions as C Pre-Processor Macros

To minimise code duplication bit operator functions can be defined in a header file as pre-processor macros

/* a=number, b=bit index 0-n */ #define BIT_SET(a,b) ((a) |= (1UL<<(b))) #define BIT_CLEAR(a,b) ((a) &= ~(1UL<<(b))) #define BIT_FLIP(a,b) ((a) ^= (1UL<<(b))) #define BIT_CHECK(a,b) (!!((a) & (1UL<<(b))))

### Print Bits in C as Left Padded Binary String

In C `printf()`

does not have a format specifier to print a string representation of binary, but we can write a function to achieve this –

const unsigned bits = 8; // print integer value as a left padded binary string void print_bits(unsigned value) { unsigned mask = 1 << (bits-1); while (mask) { printf("%d", (mask & value) != 0); mask >>= 1; } printf("\n"); } int main() { int i = 0x145; print_bits(i); } Result: 01000101

** References and Further Reading:**

[1] *Methods for Bit Manipulation & Discussion:*

https://stackoverflow.com/questions/47981/how-do-you-set-clear-and-toggle-a-single-bit/263738#263738

[2] *Theory and examples of Bitwise Operation:*

https://en.wikipedia.org/wiki/Bitwise_operation

[3] *Bit Twiddling Hacks – Advanced Bitwise Algorithms *http://graphics.stanford.edu/~seander/bithacks.html