Binary, Endianness and Bit Tricks

A bit is one binary digit, 0 or 1. A byte is 8 bits. Most bit questions in interviews are not tricks. They test whether you know how numbers are stored and what your language does to them. This lesson is about reading binary and hex, how negative numbers are stored, what |, &, ^, <<, >> and >>> really do in JavaScript, a short list of useful tricks, byte order, and how to use a bit set for permissions.

The DSA series already has a problem-focused lesson on this topic: DSA Lesson 58, Tries and Bit Manipulation. That lesson is about solving problems (single number, counting bits, subsets with bitmasks). This lesson does not repeat the problem list. It explains the machinery under those problems. For why a computer works in bits at all, see Lesson 0. For floating point numbers, which JavaScript uses for every plain number, see Lesson 2.

Words used in this lesson

• Binary is base 2: digits 0 and 1. Hexadecimal (hex) is base 16: digits 0-9 and a-f. One hex digit is exactly 4 bits, so one byte is two hex digits.
• Two's complement is the way most computers store signed integers. The top bit has a negative weight.
• Signed means the number can be negative. Unsigned means 0 or more only.
• A mask is a number whose set bits pick out some bits of another number.
• A flag is one bit that means yes or no, such as "can write".
• Endianness is the order of the bytes of a multi-byte number. Big-endian puts the most significant byte first. Little-endian puts the least significant byte first.
• Network byte order is big-endian. It is the order used in many network protocol headers.
• Popcount (population count) is the number of 1 bits in a number.

Reading binary and hex

Each bit has a weight that doubles as you go left: 1, 2, 4, 8, 16, and so on. 1011 is 8 + 2 + 1 = 11. Hex is shorter to write, so people use it for bytes and masks: ff is 1111 1111, which is 255.

JavaScript has literals for each base and two conversions:

console.log(0b1011, 0xff, 0o17, (255).toString(2), (255).toString(16), (-5).toString(2));console.log(parseInt("1011", 2), parseInt("ff", 16), Number("0b101"));console.log((5).toString(2).padStart(8, "0"));

Output:

11 255 15 11111111 ff -10111 255 500000101

Look at (-5).toString(2). It gives -101, which is a minus sign and the binary of 5. It does not show how the number is stored. To see the stored bits you must mask the number to a fixed width, which is the next section.

Two's complement: how negative numbers are stored

With 8 bits there are 256 patterns. Two's complement uses the top bit with weight -128 instead of +128. So 1111 1011 is -128 + 64 + 32 + 16 + 8 + 2 + 1 = -5. To negate a number: flip every bit, then add 1. That is -x === ~x + 1.

const bits8 = (n) => (n & 0xff).toString(2).padStart(8, "0");for (const n of [5, -5, 127, -128, -1]) console.log(String(n).padStart(4), bits8(n));

   5 00000101  -5 11111011 127 01111111-128 10000000  -1 11111111

Why people like it: addition works the same for signed and unsigned numbers, so the hardware needs one adder. There is only one zero. The range for n bits is -2^(n-1) to 2^(n-1) - 1. For 8 bits that is -128 to 127, so there is one more negative number than positive ones. (That is why negating -128 gives -128 again in 8 bits.)

Fixed-width typed arrays show wrap-around directly:

const i8 = new Int8Array([127]); i8[0] += 1; console.log("Int8 wrap", i8[0]);const u8 = new Uint8Array([0]); u8[0] -= 1; console.log("Uint8 wrap", u8[0]);console.log(-5 === ~5 + 1, ~5, ~-1, ~0);

Int8 wrap -128Uint8 wrap 255true -6 0 -1

~x flips all bits, so ~x === -x - 1. This is why ~-1 is 0, and why old code wrote if (~str.indexOf("a")) to mean "found". Do not copy that style. Write str.includes("a").

The same bits can be signed or unsigned. A value is only a number once you choose how to read it. The bits 1111 1111 1111 1110 are 65534 as unsigned 16-bit and -2 as signed 16-bit. We will see this again with DataView.

JavaScript bitwise operators use 32-bit signed integers

A plain JavaScript number is a 64-bit float (Lesson 2). The bitwise operators do not work on floats. They first convert each operand to a 32-bit signed integer (the spec calls this ToInt32), do the operation, and give back a 32-bit result. This has four effects:

1. The fraction is cut off (towards zero). Numbers outside the 32-bit range lose their high bits.
2. Anything that is not a number is converted first. NaN and Infinity become 0.
3. The result of &, |, ^, ~, << and >> is signed, so the top bit shows up as a negative number.
4. For shifts, the shift count is taken modulo 32. So 1 << 32 is 1 << 0.

console.log(2 ** 31 | 0, 2 ** 32 | 0, (2 ** 32 + 5) | 0, 1 << 31, 1 << 32, 1 << 33);console.log(5.9 | 0, -5.9 | 0, Math.floor(-5.9), 2 ** 53 | 0, "abc" | 0);console.log(2 ** 40 >> 1, Math.floor(2 ** 40 / 2));

-2147483648 0 5 -2147483648 1 25 -5 -6 0 00 549755813888

Read the last line: 2 ** 40 >> 1 is 0 because the low 32 bits of 2^40 are all zero. Dividing with Math.floor(x / 2) is correct. So never use >> 1 for halving when the value may exceed 2^31. A classic bug is a binary search written as (lo + hi) >> 1 when the array has more than 2^30 items.

Also note 5.9 | 0 is 5 and -5.9 | 0 is -5: it truncates toward zero, like Math.trunc. Math.floor(-5.9) is -6, which is different. MDN says to prefer Math.trunc over these no-op tricks, because they silently break outside the 32-bit range.

>> versus >>>

• >> is the arithmetic (sign-keeping) right shift. It copies the top bit into the empty places. It is like division by 2 that rounds toward minus infinity.
• >>> is the logical (unsigned) right shift. It puts zeros in. The result is read as an unsigned 32-bit number, 0 to 4,294,967,295.

console.log(-1 >> 1, -1 >>> 1, -1 >>> 0, -8 >> 1, -8 >>> 28);

-1 2147483647 4294967295 -4 15

x >>> 0 is the usual way to turn a signed 32-bit result into an unsigned number. You need it when a bit operation sets the top bit and you want a positive number back, such as hash values and IP addresses:

console.log(1 << 31, (1 << 31) >>> 0, 1 << 32);console.log(0xffffffff & 0xffffffff, (0xffffffff & 0xffffffff) >>> 0);

-2147483648 2147483648 1-1 4294967295

>>> does not exist in a useful form for BigInt, because a BigInt has no fixed width. Use BigInt.asUintN(bits, x) and BigInt.asIntN(bits, x) to cut a BigInt to a fixed width:

console.log(typeof (5n & 3n), 5n << 40n, BigInt.asUintN(8, -1n), BigInt.asIntN(8, 255n));

bigint 5497558138880n 255n -1n

Masks and flags

A mask picks bits. Four basic moves cover most of what you will write:

const get = (x, i) => (x >> i) & 1;const set = (x, i) => x | (1 << i);const clear = (x, i) => x & ~(1 << i);const toggle = (x, i) => x ^ (1 << i);let x = 0b1010;console.log(get(x, 1), get(x, 0), set(x, 0).toString(2), clear(x, 1).toString(2), toggle(x, 3).toString(2));console.log((0xabcd & 0xff).toString(16), ((0xabcd >> 8) & 0xff).toString(16));

1 0 1011 1000 10cd ab

Common tricks

The five tricks below show up often. Each one has a short reason, and that reason matters more than the memorised line.

const isPow2 = (n) => n > 0 && (n & (n - 1)) === 0;console.log([0, 1, 2, 3, 16, 18, 1024].map(isPow2).join(" "));const lowbit = (n) => n & -n;console.log(lowbit(12), lowbit(40), lowbit(7), (12).toString(2), (-12 >>> 0).toString(2));const clearLow = (n) => n & (n - 1);console.log(clearLow(0b101100).toString(2));

false true true false true false true4 8 1 1100 11111111111111111111111111110100101000

• n & (n - 1) clears the lowest set bit. Subtracting 1 turns the lowest 1 into 0 and every 0 below it into 1. Then AND removes the lowest 1. A power of two has exactly one set bit, so the result is 0. Check n > 0 first, because 0 would also pass.
• n & -n keeps only the lowest set bit. Look at the printed bits of 12 and -12: ...1100 and ...0100. They agree only at the lowest set bit. Fenwick trees (binary indexed trees) use this.
• Counting set bits (popcount) by repeating n &= n - 1 loops once per set bit, not once per bit:

function popcount(n) { let c = 0; n >>>= 0; while (n) { n &= n - 1; c++; } return c; }console.log(popcount(0), popcount(255), popcount(-1), popcount(0b101101));

0 8 32 4

Math.clz32 counts the leading zero bits of the 32-bit form, so the highest set bit is at position 31 - Math.clz32(n). JavaScript has no built-in popcount. Math.imul multiplies as 32-bit integers (Math.imul(65536, 65536) is 0, while 65536 * 65536 is 4294967296), which hash functions use to wrap like C.

• Swap with XOR. a ^= b; b ^= a; a ^= b; swaps two variables without a third. XOR is its own inverse, so this works. It is an interview curiosity. In real code, write [a, b] = [b, a], which is clearer. If the two names refer to the same slot (for example arr[i] and arr[j] with i === j), the XOR swap sets the value to 0.

let a = 7, b = 9; a ^= b; b ^= a; a ^= b; console.log(a, b);let p = 5; p ^= p; console.log(p);

9 70

• Find the single number. XOR of a value with itself is 0, and XOR with 0 changes nothing. So XOR over a list where every value appears twice except one gives that one value, with O(1) extra memory:

const arr = [3,3,4,4,9,5,5]; console.log(arr.reduce((s, v) => s ^ v, 0));

9

• Modulo a power of two. x & (m - 1) equals x % m when m is a power of two and x is not negative. Hash tables use this to pick a bucket:

console.log(77 & (16 - 1), 77 % 16, 7 & 1, 8 & 1, -7 & 1, -7 % 2);

13 13 1 0 1 -1

Note -7 & 1 is 1 (odd) but -7 % 2 is -1. So the test x % 2 === 1 fails for negative odd numbers; use x % 2 !== 0 or (x & 1) === 1.

For the interview problems that use these (Single Number, Number of 1 Bits, Counting Bits, Subsets), go to DSA Lesson 58.

A set of n items has 2^n subsets. Count m from 0 to 2^n - 1, and let bit i of m say whether item i is in. That is the subsets-with-bitmask problem in DSA Lesson 58.

Bit sets for permissions

A flag set packs many yes/no values in one integer. It is small, fast to compare, and easy to store in a database column or a token.

const P = { READ: 1 << 0, WRITE: 1 << 1, DELETE: 1 << 2, ADMIN: 1 << 3 };let perms = P.READ | P.WRITE;const has = (p, f) => (p & f) === f;console.log(has(perms, P.READ), has(perms, P.DELETE), has(perms, P.READ | P.WRITE));perms |= P.DELETE; perms &= ~P.WRITE;console.log(perms.toString(2).padStart(4, "0"), Object.entries(P).filter(([, v]) => perms & v).map(([k]) => k));

true false true0101 [ 'READ', 'DELETE' ]

Notes that matter in a design review:

• Test with (p & f) === f when f may hold several flags. (p & f) !== 0 means "any of them".
• The numbers are part of your stored data. Never reorder or reuse a flag value once it is in a database. Add new flags at the end.
• 31 flags is the limit with plain operators. For more, use a BigInt, or an array of 32-bit words:

class BitSet { constructor(n) { this.w = new Uint32Array((n + 31) >>> 5); }  add(i) { this.w[i >>> 5] |= 1 << (i & 31); } has(i) { return (this.w[i >>> 5] >>> (i & 31) & 1) === 1; } }const bs = new BitSet(100); bs.add(3); bs.add(64); bs.add(99);console.log(bs.has(3), bs.has(4), bs.has(64), bs.has(99), bs.w.length, bs.w.byteLength);

true false true true 4 16

One hundred flags take 16 bytes. A dense, contiguous block like this is also friendly to the CPU cache (Lesson 1).

• A bit set is less readable than a list of role names, and harder to query in SQL. Use it when size or speed matters, or when the data is a protocol format. For a normal "roles" table, plain names are usually better.

Endianness and byte order

A multi-byte number must be put in memory in some byte order. For the 32-bit value 0x12345678:

Most desktop and phone CPUs you will meet (x86-64, and ARM in its usual setting) are little-endian. Network protocols (IP, TCP, and many others) put numbers in big-endian order, so big-endian is called network byte order. Files have their own rule; each format says which order it uses.

In JavaScript, a DataView lets you choose the order for each read and write. The last argument is littleEndian, and the default is big-endian. Typed arrays like Uint32Array use the host order, which makes them risky for file and network formats.

import os from "node:os";const hex = (u8) => [...u8].map((b) => b.toString(16).padStart(2, "0")).join(" ");const buf = new ArrayBuffer(4);const dv = new DataView(buf);const u8 = new Uint8Array(buf);dv.setUint32(0, 0x12345678);            // default is big endianconsole.log("BE:", hex(u8));dv.setUint32(0, 0x12345678, true);      // true = little endianconsole.log("LE:", hex(u8));console.log(dv.getUint32(0, true).toString(16), dv.getUint32(0, false).toString(16));console.log("host:", os.endianness(), hex(new Uint8Array(new Uint32Array([0x12345678]).buffer)));

BE: 12 34 56 78LE: 78 56 34 1212345678 78563412host: LE 78 56 34 12

My machine is little-endian, so the Uint32Array stored 78 56 34 12. On a big-endian host it would store 12 34 56 78.

Reading the same four bytes in the wrong order gives a wrong number with no error. This is one of the most common bugs when you parse a binary format:

const bytes = new Uint8Array([0x00, 0x00, 0x01, 0xf4]);console.log((bytes[0] << 24 | bytes[1] << 16 | bytes[2] << 8 | bytes[3]) >>> 0);console.log(new DataView(bytes.buffer).getUint32(0), new DataView(bytes.buffer).getUint32(0, true));

500500 4093706240

Now a small binary packet: 1 byte version, 2 bytes length, 4 bytes id, all in network order. Then the signed versus unsigned view of the same bytes:

const pkt = new DataView(new ArrayBuffer(7));pkt.setUint8(0, 1); pkt.setUint16(1, 500); pkt.setUint32(3, 0xdeadbeef);console.log(hex(new Uint8Array(pkt.buffer)), pkt.getUint16(1), pkt.getUint32(3).toString(16));const s = new DataView(new Uint8Array([0xff, 0xfe]).buffer);console.log(s.getInt16(0), s.getUint16(0), s.getInt8(0), s.getUint8(0));

01 01 f4 de ad be ef 500 deadbeef-2 65534 -1 255

Text is a different case: in UTF-8 the byte order of each character is fixed, so UTF-8 has no endianness. UTF-16 does need an order for each 16-bit unit; see Lesson 3. Floats are stored as bytes too (Lesson 2).

Common mistakes

1. Using bitwise operators on numbers above 2^31 (or 2^32). The high bits are dropped without any error.
2. Forgetting >>> 0 and printing a negative number where you wanted unsigned.
3. >> 1 for halving a value that may be negative or large.
4. Missing parentheses around & and | next to === or +.
5. Assuming the host byte order when reading a file or socket. Use DataView with an explicit order.
6. Reusing or reordering flag values that are already stored.
7. Using a typed array on bytes of the wrong size. new Uint16Array(new Uint8Array([1,2,3]).buffer) threw RangeError: byte length of Uint16Array should be a multiple of 2 when I ran it. DataView reads any offset.

Interview questions

Key takeaways

• Binary is base 2, and one hex digit is exactly four bits. Two's complement gives -x === ~x + 1, one zero, and the same adder for signed and unsigned.
• JavaScript bitwise operators work on 32-bit signed integers. Larger numbers lose their high bits, shift counts are taken modulo 32, and >>> 0 makes the result unsigned.
• >> keeps the sign, >>> does not. Use Math.floor or Math.trunc for arithmetic, and BigInt for wide values.
• The tricks all come from n & (n - 1) (clear the lowest bit), n & -n (keep the lowest bit) and XOR cancelling itself.
• Endianness is byte order. Network order is big-endian. Use DataView with an explicit order for any file or network format.
• Flags are compact but become stored data. Never reorder them, and watch the 31-flag limit.
• Always use parentheses around bitwise operators.

What's next

Lesson 5: Combinatorics and Probability for Interviews. Counting and chance are the next set of basics that interviewers expect without explaining, and you can check every answer by simulation. Before that, solve the problems in DSA Lesson 58 using the machinery from this lesson.