Bits, bitmasks and bit manipulations

Contents

Terminology

Term Bits Bytes NASM GAS
bit 1 bit      
trit 1 bits      
nibble 4 bits ½ byte    
byte 8 bits 1 byte DB .byte
word 16 bits 2 byte DW .word
dword or double word 32 bits 4 bytes DD .long
qword or quad word 64 bits 8 bytes DQ  
tword or ten word 80 bits 10 bytes DT  
oword or octo word 128 bits 16 bytes DO  
yword 2 256 bits 32 bytes DY  
zword 3 512 bits 64 bytes DZ  
  1. Used in ternary arithmetic, beyond scope.
  2. Intel AVX YMM register.
  3. Intel AVX-512 ZZM register.

Binary

Binary numbers, or bits are numbers in the base-2 number system. “Orinary” numbers are in base-10, hexadecimal numbers are in base-16:

/* base-10 */
2342     = 2 * (10 ** 3) + 3 * (10 ** 2) + 4 * (10 ** 1) + 2 * (10 ** 0)  = 2342;
/* base-16 */
0x172a   = 1 * (16 ** 3) + 7 * (16 ** 2) + 2 * (16 ** 1) + 10 * (16 ** 0) = 2342;
/* base-2 */
0b101010 = 1 * ( 2 ** 5) + 1 * ( 2 ** 3) + 1 * ( 2 ** 1)                  =   42;

Nibbles

A byte consists of two nibbles, or half bytes. A nibble contains 4 bits of information, thus an 8 bit byte contains two nibbles.

/*
0x0 = 0000 ; 0x4 = 0100 ; 0x8 = 1000 ; 0xc = 1100
0x1 = 0001 ; 0x5 = 0101 ; 0x9 = 1001 ; 0xd = 1101
0x2 = 0010 ; 0x6 = 0110 ; 0xa = 1010 ; 0xe = 1110
0x3 = 0011 ; 0x7 = 0111 ; 0xb = 1011 ; 0xf = 1111
*/

uint8_t msn, lsn;
/*  most significant nibble: */   msn = (x & 0xf0) >> 4;
/* least significant nibble: */   lsn = (x & 0x0f);
/*          nibbles to byte: */     x = (msn << 4) | lsn;

Bit operations

uint8_t x, y;
/*   get bit y in x: */            x &=  (1 << y);
/*   set bit y in x: */            x |=  (1 << y);  
/* unset bit y in x: */            x &= ~(1 << y);  

Bit masks

#define FEATURE_NONE    (0x00)
#define FEATURE_A       (1 << 0)
#define FEATURE_B       (1 << 1)
#define FEATURE_C       (1 << 2)
#define FEATURE_D       (1 << 3)
#define FEATURE_E       (1 << 4)
#define FEATURE_F       (1 << 5)
#define FEATURE_G       (1 << 6)
#define FEATURE_H       (1 << 7)
#define FEATURE_ALL     (0xff)

uint8_t features = FEATURE_NONE;

void enable_feature(uint8_t feature) {
    features |= feature;
}

void disable_feature(uint8_t feature) {
    features &= ~feature;
}

if (features & FEATURE_B) {
    /* ... */
}

Counting bits

uint8_t v; 	/* Value we want to count */
uint8_t c; 	/* Bit count accumulator */
for (c = 0; v; c++) {
	v & = v - 1; /* Clear the least significan bit that is set */
}

Published in 1988, the C Programming Language 2nd Ed. by Brian W. Kernighan and Dennis M. Ritchie.

Counting bits in 14, 24 or 32-bit words using 64-bit instructions

uint64_t v; // count the number of bits set in v
uint64_t c; // c accumulates the total bits set in v

// option 1, for at most 14-bit values in v:
c = (v * 0x200040008001ULL & 0x111111111111111ULL) % 0xf;

// option 2, for at most 24-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) 
     % 0x1f;

// option 3, for at most 32-bit values in v:
c =  ((v & 0xfff) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;
c += (((v & 0xfff000) >> 12) * 0x1001001001001ULL & 0x84210842108421ULL) % 
     0x1f;
c += ((v >> 24) * 0x1001001001001ULL & 0x84210842108421ULL) % 0x1f;

Swapping values with XOR

You can do triple XOR to swap two values without using a temporary register:

a ^= b;
b ^= a;
a ^= b;

/* Swap macro */
#define SWAP(a, b) (((a) ^= (b)), ((b) ^= (a)), ((a) ^= (b)))

Reverse bits in a byte

uint8_t v;     // input bits to be reversed
uint8_t r = v; // r will be reversed bits of v; first get LSB of v
int s = sizeof(v) * CHAR_BIT - 1; // extra shift needed at end

for (v >>= 1; v; v >>= 1)
{   
  r <<= 1;
  r |= v & 1;
  s--;
}
r <<= s; // shift when v's highest bits are zero

Reverse bits in a byte using 64-bit multiply and modulus

uint8_t b; // input bits to be reversed
b = (b * 0x0202020202ULL & 0x010884422010ULL) % 1023;

By Sean Anderson, July 13, 2001.

Multi byte packing

uint8_t a, b, c, d;

/* big endian */
uint16_t  word_be = (a <<  8) | (b      );                         
uint32_t dword_be = (a << 24) | (b << 16) | (c <<  8) | (d      );

/* little endian */
uint16_t  word_be = (a      ) | (b <<  8);                         
uint32_t dword_le = (a      ) | (b <<  8) | (c << 16) | (d << 24);

Bit matrix multiplication

Given matrices and :

We can calculate as:

And for vector :

We can calculate as:

Working with bytes in programming languages

Language Example Note
C uint8_t b = 0x2a; b |= c; Masking may be required
Java static byte b = 0x2a; b |= c; Guaranteed to be 8 bit byte
PHP $b = 0x2a; $b = ($b | $c) & 0xff; No byte type, masking required (depends on size of c)
Python b = bytearray(1); b[0] = 0x2a; b[0] |= c[0]; Guaranteed to be 8 bit byte
Ruby b = 0x2a; b = (b | c) & 0xff No byte type, masking required (depends on size of c)

  Leave your Message here...