Binary and Bitwise Operations

Kernel code manipulates bits constantly: hardware registers use individual bits as flags, page table entries encode permissions in specific bit fields, and memory allocators use bitmap tracking. This page covers the binary concepts you need daily.

Data Sizes

Unit	Bits	C Type (stdint)
Byte	8	`uint8_t`
Half-word	16	`uint16_t`
Word	32	`uint32_t`
Double-word	64	`uint64_t`

In ARM64 assembly: w registers are 32-bit (word), x registers are 64-bit (double-word).

Hexadecimal Quick Reference

Memory addresses and register values are always shown in hex. One hex digit = 4 bits.

Hex  Binary   Dec    Hex  Binary   Dec
0    0000     0      8    1000     8
1    0001     1      9    1001     9
2    0010     2      A    1010     10
3    0011     3      B    1011     11
4    0100     4      C    1100     12
5    0101     5      D    1101     13
6    0110     6      E    1110     14
7    0111     7      F    1111     15

Examples: 0xFF = 255, 0x100 = 256, 0x1000 = 4096 (4 KB page size).

Bitwise Operations

These are the operations we use in kernel code every day:

Operation	C Operator	Use Case
AND	`&`	Masking (extract specific bits), checking flags
OR	`\|`	Setting specific bits
XOR	`^`	Toggling bits
NOT	`~`	Inverting all bits (used with AND to clear bits)
Left shift	`<<`	Multiply by power of 2, create bit masks
Right shift	`>>`	Divide by power of 2, extract bit fields

Common Patterns in Kernel Code

/* Set bit N in a register */
reg |= (1U << N);

/* Clear bit N */
reg &= ~(1U << N);

/* Check if bit N is set */
if (reg & (1U << N)) { ... }

/* Extract bits M through N (inclusive) */
uint32_t field = (reg >> N) & ((1U << (M - N + 1)) - 1);

/* Combine fields into a register value */
reg = (field1 << shift1) | (field2 << shift2);

/* Page-aligned address (round down to 4 KB) */
uint64_t aligned = addr & ~0xFFFULL;

/* Check if address is page-aligned */
if (addr & 0xFFF) { /* not aligned */ }

/* Convert physical address to page table entry (ARM64) */
uint64_t pte = (phys_addr >> 12) << 12;  /* upper bits = address */
pte |= 0x3;                               /* set valid + table/block */

Two's Complement (Signed Numbers)

ARM64 uses two's complement for signed integers. The most significant bit is the sign bit (0 = positive, 1 = negative).

8-bit examples:
  0b00000001 = +1
  0b01111111 = +127
  0b10000000 = -128
  0b11111111 = -1

Negate a number: invert all bits, add 1.
  +5 = 0b00000101
  -5 = 0b11111011  (invert 00000101 -> 11111010, add 1 -> 11111011)

The key insight: ADD and SUB instructions work identically for signed and unsigned. The CPU does not care. The C type determines interpretation.

Endianness

ARM64 is little-endian by default. A 32-bit value 0x12345678 at address 0x1000 is stored as:

0x1000: 0x78  (least significant byte first)
0x1001: 0x56
0x1002: 0x34
0x1003: 0x12  (most significant byte last)

When reading raw bytes from memory or a device, always consider endianness. Network byte order is big-endian, so network code must convert using htonl/ntohl.

Alignment

An N-byte value should be at an address divisible by N. ARM64 allows unaligned access for most instructions, but it is slower. Some atomic instructions require alignment.

/* Force alignment on a struct */
struct page_table_entry {
    uint64_t data;
} __attribute__((aligned(16)));

/* Ensure a pointer is aligned */
if ((uintptr_t)ptr & (sizeof(uint32_t) - 1)) {
    /* ptr is not 4-byte aligned */
}

Bitmap Operations (for Memory Allocators)

#define BITMAP_WORDS 32  /* 1024 bits */
uint32_t bitmap[BITMAP_WORDS];

/* Set bit index i */
bitmap[i / 32] |= (1U << (i % 32));

/* Clear bit i */
bitmap[i / 32] &= ~(1U << (i % 32));

/* Test bit i */
int test = (bitmap[i / 32] >> (i % 32)) & 1;

/* Find first zero bit */
int find_free(void) {
    for (int w = 0; w < BITMAP_WORDS; w++) {
        if (bitmap[w] != 0xFFFFFFFF) {
            int bit = __builtin_ctz(~bitmap[w]);
            return w * 32 + bit;
        }
    }
    return -1; /* no free bits */
}

__builtin_ctz (count trailing zeros) is a GCC built-in that compiles to a single ARM64 instruction. Use it instead of manual loops.

Memory-Mapped I/O Rules

When accessing hardware registers (which are memory-mapped on ARM64):

Always use volatile - prevents the compiler from optimizing away reads/writes
Always use unsigned types - signed right shift is implementation-defined
Access registers at their natural size (use uint32_t for 32-bit registers)
Do not rely on read-modify-write being atomic - use atomic operations for that

/* Correct */
volatile uint32_t *uart = (volatile uint32_t *)0x09000000;
*uart = 'A';

/* Wrong (might be optimized away) */
uint32_t *uart = (uint32_t *)0x09000000;
*uart = 'A';