DSA MASTERY · CH 11 · BIT MANIPULATION · CHAPTER 9
⚙️ Systems Bit Manipulation Problems
Fully-worked problems from real systems engineering — IPv4 · Subnets · Packet Headers · MAC · Memory Alignment
IPv4 Encoding
Subnet / CIDR
VLAN / TCP / DSCP
MAC Address
Aligned Allocator
Ring Buffer
Each problem: bit layout → approach → complete C code → dry run → edge cases
PROBLEM SET 1 — IPv4 ENCODING & DECODING
P1.1 — ipv4_to_uint32(char* ip) Medium
Convert "192.168.10.5" into a single uint32_t without library functions.
IPv4 "192.168.10.5" layout:
Bit: 31..24 23..16 15..8 7..0
[ 192 ][ 168 ][ 10 ][ 5 ]
result = (192<<24)|(168<<16)|(10<<8)|5 = 0xC0A80A05
uint32_t ipv4_to_uint32(const char* ip) {
uint32_t result = 0;
int octet = 0, shift = 24;
while (*ip) {
if (*ip == '.') { result |= (uint32_t)octet << shift; shift -= 8; octet = 0; }
else { octet = octet * 10 + (*ip - '0'); }
ip++;
}
return result | (uint32_t)octet;
}
void uint32_to_ipv4(uint32_t ip, char* buf) {
sprintf(buf, "%u.%u.%u.%u",
(ip >> 24) & 0xFF, (ip >> 16) & 0xFF,
(ip >> 8) & 0xFF, ip & 0xFF);
}
PROBLEM SET 2 — SUBNET & CIDR OPERATIONS
P2.1 — isValidIP(char* ip, char* netId, int prefix) Hard
Does IP belong to the given subnet? E.g. isValidIP("192.168.10.5","192.168.10.0",28) → true.
192.168.10.5 & mask(/28=0xFFFFFFF0) = 0xC0A80A00
192.168.10.0 & mask(/28=0xFFFFFFF0) = 0xC0A80A00 → match ✓
bool isValidIP(char* ip, char* netId, int prefix) {
uint32_t a = ipv4_to_uint32(ip), b = ipv4_to_uint32(netId);
uint32_t mask = (prefix == 0) ? 0 : ~((1U << (32-prefix)) - 1);
return (a & mask) == (b & mask);
}
uint32_t networkAddr (uint32_t ip, int p) { return ip & ~((1U<<(32-p))-1); }
uint32_t broadcastAddr(uint32_t ip, int p) { return networkAddr(ip,p) | ((1U<<(32-p))-1); }
uint32_t hostCount (int p) { return (1U << (32-p)) - 2; }
PROBLEM SET 3 — PACKET HEADER FIELD EXTRACTION
P3.1 — Parse VLAN 802.1Q Tag Medium
Extract PCP (3-bit), DEI (1-bit), VID (12-bit) from a 16-bit tag.uint16_t tag = ntohs(raw);
uint8_t pcp = (tag >> 13) & 0x07;
uint8_t dei = (tag >> 12) & 0x01;
uint16_t vid = tag & 0x0FFF;
// Rebuild: htons((pcp<<13)|(dei<<12)|(vid&0xFFF))
P3.2 — Extract DSCP and ECN from IPv4 TOS byte Easy
TOS byte: [DSCP: 6 bits][ECN: 2 bits]
DSCP = (tos >> 2) & 0x3F
ECN = tos & 0x03
uint8_t dscp = (tos >> 2) & 0x3F;
uint8_t ecn = tos & 0x03;
// Rebuild: tos = (dscp << 2) | (ecn & 3)
P3.3 — Inspect TCP Flags Medium
#define TCP_FIN 0x01
#define TCP_SYN 0x02
#define TCP_RST 0x04
#define TCP_PSH 0x08
#define TCP_ACK 0x10
const char* tcpState(uint8_t f) {
if ((f & 0x12) == 0x02) return "SYN";
if ((f & 0x12) == 0x12) return "SYN+ACK";
if (f & 0x04) return "RST";
if (f & 0x01) return "FIN";
return "ACK/data";
}
PROBLEM SET 4 — MAC ADDRESS OPERATIONS
P4.1 — mac_to_uint64 / uint64_to_mac Medium
Pack/unpack 6-byte MAC into uint64_t. Detect multicast, broadcast, extract OUI.AA:BB:CC:DD:EE:FF → 0x0000AABBCCDDEEFF
I/G bit (bit 0 of byte[0]) = 1 means multicast
Broadcast = 0x0000FFFFFFFFFFFFULL
uint64_t mac_to_uint64(const uint8_t m[6]) {
uint64_t r=0; for(int i=0;i<6;i++) r=(r<<8)|m[i]; return r; }
void uint64_to_mac(uint64_t v, uint8_t m[6]) {
for(int i=5;i>=0;i--){m[i]=v&0xFF;v>>=8;} }
bool isMulticast(const uint8_t m[6]) { return (m[0]&1)!=0; }
uint32_t getOUI(const uint8_t m[6]) {
return ((uint32_t)m[0]<<16)|((uint32_t)m[1]<<8)|m[2]; }
PROBLEM SET 5 — GENERAL & INTERVIEW PROBLEMS
P5.1 — Binary Palindrome Medium P5.2 — Generate All Subsets Medium
// P5.1: Is 32-bit integer a binary palindrome?
bool isBinPalindrome(uint32_t x) {
uint32_t r=x;
r=((r&0xFFFF0000)>>16)|((r&0x0000FFFF)<<16);
r=((r&0xFF00FF00)>> 8)|((r&0x00FF00FF)<< 8);
r=((r&0xF0F0F0F0)>> 4)|((r&0x0F0F0F0F)<< 4);
r=((r&0xCCCCCCCC)>> 2)|((r&0x33333333)<< 2);
r=((r&0xAAAAAAAA)>> 1)|((r&0x55555555)<< 1);
return x==r;
}
// P5.2: All subsets using bitmask enumeration
void allSubsets(int* a, int n) {
for(int mask=0; mask<(1<<n); mask++) {
for(int i=0; i<n; i++) if(mask&(1<<i)) printf("%d ",a[i]);
printf("\n");
}
}
P5.3 — Count Subarrays with XOR = k Hard
Key insight:XOR(i..j) = prefixXOR[j] ^ prefixXOR[i-1]. Use prefix XOR + hash map.
int countXOR(int* nums, int n, int k) {
int freq[1024]={0}; freq[0]=1;
int pre=0, cnt=0;
for(int i=0;i<n;i++) { pre^=nums[i]; cnt+=freq[pre^k]; freq[pre]++; }
return cnt;
}
PROBLEM SET 6 — MEMORY ALIGNMENT & ALLOCATOR TRICKS
P6.1 — Aligned Memory Allocator Hard
Over-allocate, adjust pointer forward to alignment boundary, store original pointer just before user block.Strategy: malloc extra bytes → find aligned addr → store orig ptr before it
aligned_malloc(100, 64): raw=malloc(172) → aligned=alignUp(raw+8,64) → store raw → return aligned
aligned_free(ptr): raw = ((void**)ptr)[-1]; free(raw);
void* aligned_malloc(size_t sz, size_t al) {
if(!al||(al&(al-1))) return NULL;
void* raw = malloc(sz + al + sizeof(void*));
if(!raw) return NULL;
uintptr_t adj = (uintptr_t)raw + sizeof(void*);
uintptr_t aln = (adj + al - 1) & ~(al - 1);
((void**)aln)[-1] = raw;
return (void*)aln;
}
void aligned_free(void* p) { if(p) free(((void**)p)[-1]); }
P6.2 — Ring Buffer with Power-of-2 Sizing Medium
Use(idx+1) & mask instead of % size for index wrapping — valid only when size is power of 2.
typedef struct { uint32_t* data; uint32_t mask,head,tail; } ring_t;
bool push(ring_t* r, uint32_t v) {
uint32_t n=(r->head+1)&r->mask;
if(n==r->tail) return false;
r->data[r->head]=v; r->head=n; return true;
}
bool pop(ring_t* r, uint32_t* v) {
if(r->head==r->tail) return false;
*v=r->data[r->tail]; r->tail=(r->tail+1)&r->mask; return true;
}
// DPDK rte_ring uses exactly this pattern.