Bits and Bytes

Rahul Pandey | April 10, 2017

Computers work with the simplest possible unit of data: a bit (short for binary digit). A bit has value 0 or 1. Groups of 8 bits together make up a byte. Computer memory is discussed in terms of bytes, such as a kilobyte or megabyte. Hexadecimal, or base 16, is used to represent 4 bits as a time, so a byte is represented as 2 hexadecimal digits. Since 24 is 16, each digit in hexadecimal can take on 16 possible values: 0-9 represent zero to nine, and A-F represent ten to fifteen. For example, a byte could be 0xA3, where the 0x prefix is used to indicate hexadecimal (the value of 0xA3 in decimal is 163).


Powers of 2

You should memorize the first few powers of 2 (see bottom of this article), and some size prefixes:

Prefix Official definition Informal meaning
kilobyte 103 bytes 210 bytes
megabyte 106 bytes 220 bytes
gigabyte 109 bytes 230 bytes
terabyte 1012 bytes 240 bytes
petabyte 1015 bytes 250 bytes

Depending on who you talk to, a kilobyte is either 103 (1000) bytes, or 210 (1024) bytes. See Jeff Atwood’s blog post about this as a source of discrepancy between hard drives and operating systems [1]. In whatever system used, know that each increase in memory is roughly 1000 times bigger, either 103 or 210.

Bit manipulation

Common bit manipulations are AND, OR, XOR, NOT, and bit shifts [2]. These operators take in two bits and output a bit. The meanings of these are clear, except XOR, which returns a 1 if exactly one of the input bits was 1 (but not both). OR is represented by |, AND by &, NOT by ~, and XOR by ^. Think about why the following bit properties are true:

x ^ 0s = x x & 0s = 0 x | 0s = x
x ^ 1s = ~x x & 1s = x x | 1s = 1
x ^ x = 0 x & x = x x | x = x

Some questions use these binary operators in their solution.

You are given a list of numbers, where each number appears twice, except one number appears once. How can you find the number that appears once in linear time and constant space?
The answer is clear if we use XOR. Starting with 0, we XOR each number in the list with the accumulator (which starts at 0). All the duplicates in the list will "cancel" each other out with XOR, and the remaining number will be the singleton. This solution requires linear time and the only extra memory required is a single integer.

Powers of 2 to know:

Power Value
0 1
1 2
2 4
3 8
4 16
5 32
6 64
7 128
8 256
9 512
10 1024