Binary System

How to convert a number to binary manually: While the number is greater than 0 — if it is odd, write bit 1; if it is even, write bit 0. Then divide the number by 2 (floor the result if it’s odd). Bits are written from right to left.

Example:
Convert n = 368 to binary


368 is even -> write bit 0 -> result is '0'. 368/2 = 184  
184 is even -> write bit 0 -> result is '00'. 184/2 = 92  
92 is even -> write bit 0 -> result is '000'. 92/2 = 46  
46 is even -> write bit 0 -> result is '0000'. 46/2 = 23  
23 is odd -> write bit 1 -> result is '10000'. 23/2 = 11  
11 is odd -> write bit 1 -> result is '110000'. 11/2 = 5  
5 is odd -> write bit 1 -> result is '1110000'. 5/2 = 2  
2 is even -> write bit 0 -> result is '01110000'. 2/2 = 1  
1 is odd -> write bit 1 -> result is '101110000'. 1/2 = 0 (done)


Conclusion: 368 in binary is 101110000

Convert 147 to binary


147 is odd -> write bit 1 -> result is '1'. 147/2 = 73  
73 is odd -> write bit 1 -> result is '11'. 73/2 = 36  
36 is even -> write bit 0 -> result is '011'. 36/2 = 18  
18 is even -> write bit 0 -> result is '0011'. 18/2 = 9  
9 is odd -> write bit 1 -> result is '10011'. 9/2 = 4  
4 is even -> write bit 0 -> result is '010011'. 4/2 = 2  
2 is even -> write bit 0 -> result is '0010011'. 2/2 = 1  
1 is odd -> write bit 1 -> result is '10010011'. 1/2 = 0 (done)


Conclusion: 147 in binary is 10010011

Based on binary conversion, we see that: every natural number x has a unique way to be expressed as the sum of powers of 2.


368 in binary is 101110000  
368 = 2^8 + 2^6 + 2^5 + 2^4 + 2^0



147 in binary is 10010011  
147 = 2^7 + 2^4 + 2^1 + 2^0


Important: Bit positions in binary numbers are indexed from 0 from right to left.

Bit 0 is the least significant bit (rightmost).  
Bit next to it is bit 1, etc.  
The leftmost bit (most significant) is the one with the highest index.


368 in binary: 101110000  
368 = 2^8 + 2^6 + 2^5 + 2^4 + 2^0  
Bit 0 of 368 is 0  
Bit 1 of 368 is 0  
Bit 2 of 368 is 0  
Bit 3 of 368 is 0  
Bit 4 of 368 is 1  
Bit 5 of 368 is 1  
Bit 6 of 368 is 1  
Bit 7 of 368 is 0  
Bit 8 of 368 is 1



147 in binary: 10010011  
147 = 2^7 + 2^4 + 2^1 + 2^0  
Bit 0 of 147 is 1  
Bit 1 of 147 is 1  
Bit 2 of 147 is 0  
Bit 3 of 147 is 0  
Bit 4 of 147 is 1  
Bit 5 of 147 is 0  
Bit 6 of 147 is 0  
Bit 7 of 147 is 1


Every natural number has a unique representation as the sum of powers of 2.  
You can determine which bits are 1 by checking which 2^i values are included.

New method to convert x to binary:

Step 1: Find the largest k such that 2^k ≤ x → Binary representation has (k+1) bits (bit positions 0 to k)

Step 2: For i = k, k-1, ..., 0  
→ if x ≥ 2^i → bit i = 1 and x = x — 2^i  
→ otherwise → bit i = 0 (x stays the same)

Convert 368 to binary

k = 8 (2^8 = 256 ≤ 368, 2^9 = 512 > 368) → binary has 9 bits


Check i = 8, x = 368 ≥ 2^8 → bit 8 = 1 (1????????) → x = 368 — 256 = 112  
Check i = 7, x = 112 < 2^7 → bit 7 = 0 (10???????)  
Check i = 6, x = 112 ≥ 2^6 → bit 6 = 1 (101??????) → x = 112 — 64 = 48  
Check i = 5, x = 48 ≥ 2^5 → bit 5 = 1 (1011?????) → x = 48 — 32 = 16  
Check i = 4, x = 16 ≥ 2^4 → bit 4 = 1 (10111????) → x = 16 — 16 = 0  
Check i = 3, x = 0 < 2^3 → bit 3 = 0 (101110???)  
Check i = 2, x = 0 < 2^2 → bit 2 = 0 (1011100??)  
Check i = 1, x = 0 < 2^1 → bit 1 = 0 (10111000?)  
Check i = 0, x = 0 < 2^0 → bit 0 = 0 (101110000)


Convert 147 to binary  
k = 7 (2^7 = 128 ≤ 147, 2^8 = 256 > 147) → binary has 8 bits


Check i = 7, x = 147 ≥ 2^7 → bit 7 = 1 (1???????) → x = 147 — 128 = 19  
Check i = 6, x = 19 < 2^6 → bit 6 = 0 (10??????)  
Check i = 5, x = 19 < 2^5 → bit 5 = 0 (100?????)  
Check i = 4, x = 19 ≥ 2^4 → bit 4 = 1 (1001????) → x = 19 — 16 = 3  
Check i = 3, x = 3 < 2^3 → bit 3 = 0 (10010???)  
Check i = 2, x = 3 < 2^2 → bit 2 = 0 (100100??)  
Check i = 1, x = 3 ≥ 2^1 → bit 1 = 1 (1001001?) → x = 3 - 2 = 1  
Check i = 0, x = 1 ≥ 2^0 → bit 0 = 1 (10010011) → x = 1 - 1 = 0 (done)