Month: August 2020

First we define bits, bit fields 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 IOT 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 field 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, IO from data storage, ports, or peripherals.

Bits in a Byte – Memory Address

Bitwise shift 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 an 8 bit length 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 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) &amp;= ~(1UL<<(b)))
#define BIT_FLIP(a,b) ((a) ^= (1UL<<(b)))
#define BIT_CHECK(a,b) (!!((a) &amp; (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 &amp; 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