Skip to content

What the hell is bit shifting?

Tarun Verma

Published: at 03:43 PM

Note: This write-up assumes familiarity with DNS, in particular the entire question-answer (“resolution”) process. Some helpful pages to refer:


I found myself in a bit of a funk late last year, and realised that I haven’t written any code in a while that I had felt truly proud of. I mean sure, there’s the usual LeetCode grind I’ve taken up every now and then: that Sisyphean ordeal every engineer working in tech takes up to go through those somewhat mechanical interview rounds. I doubt most engineers enjoy it (I certainly don’t), so to save myself any more unwarranted self-loathing, I figured I should do a fair bit more of hobby coding. I was introduced to CodeCrafters by a coworker, and decided to solve the DNS server challenge. It was an easy pick: I’ve been working in Edge engineering for a while now, so I figured this challenge would teach me some practical bits about a service I’m more or less familiar with…

No matter how well you thought you knew something, it’s surprising how little you actually know.

I did manage to finish the challenge. The code is still pretty fucking shit, you can see it for yourself here. It might not make a ton of sense unless you go through the challenge yourself, but it serves as a basic DNS forwarding server that receives some DNS questions, forwards them to a resolver, retrieves the answer and sends it back to the asking client. It’s not a complete implementation - not yet, at least. I may get to expanding upon it and turning it into a complete forwarding server at some point. For now though I’m happy with this being finished in the context of the challenge, and so I’m going to talk about some of my learnings while going through this ordeal.

Enough yapping, let me talk about the first interesting thing - setting specific bits inside a DNS header. To reiterate, a DNS header is a 12 byte field that’s arranged like this:

FieldSize (bits)Description
Transaction ID16Unique identifier for request/response
Flags16Controls query type, recursion, etc.
Questions16Number of entries in the Question section
Answer RRs16Number of resource records in Answer section
Authority RRs16Number of resource records in Authority section
Additional RRs16Number of resource records in Additional section

Of importance to us are the flags, which have to be set in the context of the request received:

Bit(s)FieldDescription
0QRQuery (0) or Response (1)
1-4OPCODEQuery type (standard, inverse, etc.)
5AAAuthoritative Answer
6TCTruncated Response (set to 1 if message is larger than 512 bytes, 0 in UDP responses)
7RDRecursion Desired (indicate to server to resolve the request recursively)
8RARecursion Available
9-11Z (Reserved)Used to indicate DNSSEC (was a reserved bit during inception)
12-15RCODEResponse code (success, format error, etc.)

This stage of the challenge asked us to craft a DNS header with some specific values for the various fields described above. When I started thinking about the problem, I knew I had to use a bytearray(12) to achieve this. (remember: DNS headers are of fixed size, 12 bytes). But I also wanted this to be somewhat easier to work with: a user should be able to call something like:

test_dns_packet = DNSPacket()

test_dns_packet.set_header(
	ID=1234,
	QR=0,
	OPCODE=1,
	AA=0,
	TC=0,
	RD=1,
	RA=0,
	Z=0,
	RCODE=0,
	QDCOUNT=1,
	ANCOUNT=0,
	NSCOUNT=0,
	ARCOUNT=0
)

which should allow them to set flags individually by sending values that are more friendly (instead of passing bits/binary values around). This is not something I had worked with in a long time: how do I toggle specific bits within the 2 bytes (16 bits) reserved for 8 flag values individually, and also make it so that a user invoking the method can pass a regular int value (a full fledged object in Python) to toggle those? A combination of memory, bunch of Google searches, and some LLM queries led me back to bit arithmetic - something I had studied way back in college, and came across every now and then, but never paid much attention to otherwise. Surprising how far bit shifts and logical ANDs can get you.

Say you have a 2 byte value ID that’s set to hex 0xABCD. If you remember those lectures on endianness, you’d remember that 0xAB is the MSB (most significant byte) and 0xCD is the LSB (guess). Big endian (network byte order) places the MSB first, little endian prioritises LSB, so the byte order would look like:

  1. Big endian: 0xAB 0xCD
  2. Little endian: 0xCD 0xAB

Here’s 0xABCD in binary: 1010101111001101

or: 10101011 (0xAB) 11001101 (0xCD)

Now let’s discuss left shifting and right shifting:

  1. Left shifting (<<): Moves bits to the left, and pads zeroes on the right. So 0b1 << 8 would move 1 8 times to the left, resulting in 0b100000000. Mathematically, left shifting by n bits multiplies the original value with 2^n. Indeed, 0b100000000 evaluates to 256, which is 1 (original value) multiplied by 2^8.
  2. Right shifting (>>): Moves bits to the right, padding zeroes on the left. So 0b11110000 >> 4 would get rid of the last 4 zeroes, and pad 4 in beginning, giving us 0b00001111. Right shifting by n bits does the opposite: it divides the value by 2^n. Since 0b11110000 evaluates to 240, right shifting by 4 would have us divide 240 by 2^4, yielding us the value 15 (0b00001111).

So to extract 0xAB into a single byte, MSB:

ID = 0xABCD # 10101011 11001101
MSB = ID >> 8 # 00000000 10101000
MSB = MSB & 0xFF

The last step is important here: MSB & 0xFF evaluates to (00000000 10101000) & 11111111, which gives us 10101000, packing MSB into a single byte. Similarly, if we just want to extract the LSB, we don’t have to engage in bit shifting, as just logically ANDing it with 0xFF would yield us the last 8 bits:

LSB = ID & 0xFF

And then setting the transaction ID portion of the DNS header is as simple as:

# self.header is a bytearray() of size 12
self.header[0] = MSB
self.header[1] = LSB

From the logic that we’ve discussed so far, the bit layout for flags can be set as follows:

'''
Suppose we receive the following values:
QR = 1
OPCODE = 2
AA = 1
TC = 0
RD = 1
RA = 0
Z = 0
RCODE = 3
'''

FLAGS = (QR << 15) | (OPCODE << 11) | (AA << 10) | (TC << 9) | (RD << 8) | (RA << 7) | (Z << 4) | (RCODE & 0xF)

This maybe a bit difficult to parse at first, but it’s quite intuitive once you understand the shifting business: whatever values you receive in the set_header() function are shifted according to the bit space assigned to them, and we build FLAG by successively logically ORing:

  1000 0000 0000 0000  (QR << 15)
| 0001 0000 0000 0000  (OPCODE << 11)
| 0000 1000 0000 0000  (AA << 10)
| 0000 0000 0000 0000  (TC << 9)
| 0000 0001 0000 0000  (RD << 8)
| 0000 0000 0000 0000  (RA << 7)
| 0000 0000 0000 0000  (Z << 4)
| 0000 0000 0000 0011  (RCODE & 0xF)
--------------------------------------
  1001 1001 0000 0011  (Final Binary)

This gives the final FLAG value as 1001 1001 0000 0011, which is the hex value 0x9903. We can then pack these values into the header in a manner similar to the transaction ID:

self.header[2] = (FLAGS >> 8) & 0xFF
self.header[3] = FLAGS & 0xFF

QDCOUNT, ANCOUNT, NSCOUNT, ARCOUNT are similarly straightforward to pack.

All in all, my set_header() method finally looks like:

def set_header(self,
                   ID=0,
                   QR=0,
                   OPCODE=0,
                   AA=0,
                   TC=0,
                   RD=0,
                   RA=0,
                   Z=0,
                   RCODE=0,
                   QDCOUNT=0,
                   ANCOUNT=0,
                   NSCOUNT=0,
                   ARCOUNT=0
                   ):
        # set PID
        self.header[0] = (ID >> 8) & 0xFF
        self.header[1] = ID & 0xFF

        #set flags
        FLAGS = (QR << 15) | (OPCODE << 11) | (AA << 10) | (TC << 9) | (RD << 8) | (RA << 7) | (Z << 4) | (RCODE & 0xF)
        self.header[2] = (FLAGS >> 8) & 0xFF
        self.header[3] = FLAGS & 0xFF

        #set QDCOUNT
        self.header[4] = (QDCOUNT >> 8) & 0xFF
        self.header[5] = QDCOUNT & 0xFF

        #set ANCOUNT
        self.header[6] = (ANCOUNT >> 8) & 0xFF
        self.header[7] = ANCOUNT & 0xFF

        #set NSCOUNT
        self.header[8] = (NSCOUNT >> 8) & 0xFF
        self.header[9] = NSCOUNT & 0xFF

        #set ARCOUNT
        self.header[10] =(ARCOUNT >> 8) & 0xFF
        self.header[11] = ARCOUNT & 0xFF

Which of course is not neat, and requires some work, etc. But I’m satisfied with where it has landed at the moment. The few hours I spent trying to figure this out, reading the RFC and understanding bit shifts felt rewarding, a word that I don’t use often when discussing tech with my peers and friends these days.

I hope this was helpful. I intend to write another post or two about some other things I’ve learnt through this challenge before I move on, but I’m also open to covering something specific if you’d like me to. Feel free to write to me for suggestions, feedback etc.