Binary numbers

A binary number is just a number in base-2. Normal (decimal) numbers, like 25 or 672 are in base-10: each digit represents a tens place. So in binary, each digit (called a bit) represents a twos place. In both of them there's a pattern involving raising the base to a power; take 672, for example. The 2 is in the ones place, the 7 is in the tens place, and the 6 is in the hundreds place. In base-10, the 'places' are all powers of 10 (even the ones place, since 1 is just 10⁰). This can be shown like so:
2*10⁰ + 7*10¹ + 6*10² = 672
or, in the other way if that's easier to read:
6*10² + 7*10¹ + 2*10⁰ = 672

How does that apply to binary? Well in base-10, all the digits range from 0-9, so in base-2, all the digits range from 0-1. Take the binary number 101100. Going right to left, we have:
0*2⁰ + 0*2¹ + 1*2² + 1*2³ + 0*2⁴ + 1*2⁵ = 44.

Counting in binary isn't too hard. There's also a pattern to it. Here's counting to 15:
0000 = 0 0001 = 1 0010 = 2 0011 = 3 0100 = 4 0101 = 5 0110 = 6 0111 = 7 1000 = 8 1001 = 9 1010 = 10 1011 = 11 1100 = 12 1101 = 13 1110 = 14 1111 = 15 You should see the pattern. You can also count past 15, but you'd need another bit. After adding one, you could count to 31. If you add another, you could count to 63. How can this be known? In general, for an unsigned binary number with n bits, it can represent any number from 0 to 2ⁿ-1. Unsigned just means that it doesn't have a sign bit, so it can only be a positive integer. I'll get to signed numbers sometime idk. So with 4 bits, that's 2⁴-1 = 15, so 15 is the maximum number it can represent. Starting from 2⁰, some powers of 2 are:
1: 0 2: 1 4: 2 8: 3 16: 4 32: 5 64: 6 128: 7 256: 8 512: 9 1024: 10 2048: 11 4096: 12 8192: 13 16384: 14 32768: 15 65536: 16 ... 2147483648: 31 4294967296: 32 ... 9223372036854775808: 63 18446744073709551616: 64 You might recognize 2³¹: it's 1 off from the integer overflow number. On a lot of games, numbers are stored in regular 32 bit signed ints, so 2³¹-1 is the maximum number that can be stored. If you reach it, then it usually like wraps around and becomes negative. It's also part of the deal with computers. A long time ago, there were 8 bit and 16 bit computers. They usually did math with integers of that size. But it also affected memory addressing; like if they wanted to access the 50000th byte of memory. I think 8 bit computers used 16 bit addressing, since being limited to 255 bytes of ram would be horrible. But 16 bit addressing was pretty much limited to 65535 bytes of ram (or like 64 kb). (although the 8086 had memory segmentation, allowing 20 bit addressing or about 1 MB of ram). So then people came up with 32 bit processors, and those can usually address up to like 4 gb of ram. But not too long ago, that wasn't enough, so then came 64 bit processors that can address up to like... 2⁶⁴-1 bytes I guess, and we probably won't EVER need that much.
*note that there are some exceptions to this though, like PAE which allows 32 bit processors to address even more memory. Idk how that stuff really works and what I said is probably kinda wrong but oh well.

Converting a number from binary

Let's say you just type out some random 1s and 0s, or you get some ones and zeroes from somewhere, and you wanna find the decimal form of it. Remember that each "digit" is a power of 2, then start from the least significant digit (usually the rightmost one if it's written out, which is what I do with all binary numbers on this page), assigning it the value of 1. If there's a 1 in the digit, then your total is now 1, otherwise it's 0. Then go to the next digit, representing the next power of 2; if the 2nd digit is 1, then add 2 to the total, otherwise add nothing. Do the same thing with the next digit except with 4, then with 8, and so on until you reach the end. I'll try to write it all out with the binary number 1011010:

  total =  0
1011010
      0 = +0  (1s place)
     1  = +2  (2s place)
    0   = +0  (4s place)
   1    = +8  (8s place)
  1     = +16 (16s place)
 0      = +0  (32s place)
1       = +64 (64s place)
  total = 90

So, 1011010 is 90 in binary. This method isn't too hard to do in your head. I don't know if it's the best way of doing it, though.

Converting a number to binary

Kinda do the opposite of the above method. I guess just iteratively subtract powers of 2 starting from the biggest that fits in the number, and working towards 0? Let's try it with 90.

total = 90
       -64 = 1000000	64s place
total = 26
can't subtract 32	32s place
       -16 = 1010000	16s place
total = 10
       - 8 = 1011000	8s place
total =  2
can't subtract 4	4s place
       - 2 = 1011010	2s place
total =  0:  1011010 is the complete binary
can't subtract 1        1s place

101101

Remember that each digit is just a 'place' of a power of 2. In this, you have a total that starts at the number you're trying to convert to binary, and then you start subtracting the biggest power of 2 that fits in it. From that, you have the number of bits that can fit in the number, and you begin working down the powers of 2: skipping them if they're too big to be subtracted from the number, or subtracting them from the number and setting the corresponding bit to 1 otherwise. Do this until the total is 0. Or refer to this wikihow article; this method is method #2 in it apparently. I'm sure it has guides for converting from binary too.

Logic stuff

You probably know stuff like logic gates: 'and' gates, 'or' gates, 'not' gates, and 'xor' gates. Xor stands for eXclusive OR, and it's true if and only if ONE of its operands are true. Not both. These logic gates are called logical operators.
But I'll but truth tables for them here anyways because I want this page to have more content. If 1 is TRUE and 0 is FALSE, then you have the following:

AND gate [&&]

0 AND 0 = 0
0 AND 1 = 0
1 AND 0 = 0
1 AND 1 = 1

OR gate [||]

0 OR 0 = 0
0 OR 1 = 1
1 OR 0 = 1
1 OR 1 = 1

NOT gate (it's unary, meaning it takes only 1 operand) [!]

NOT 0 = 1
NOT 1 = 0

XOR gate

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

NAND gate (short for 'not and')

0 NAND 0 = 1
0 NAND 1 = 1
1 NAND 0 = 1
1 NAND 1 = 0

NOR gate (short for 'not or')

0 NOR 0 = 1
0 NOR 1 = 0
1 NOR 0 = 0
1 NOR 1 = 0

What's given in brackets is the operator to do it in C or C-like languages, btw. It doesn't work in Python unless you make them one character long, though: |, &, ^; in it, they also seem to be the bitwise operators, so I guess Python doesn't make a distinction between bitwise/logical operators since they probably do the same thing on booleans.

Anyways it's not that bad. Booleans and conditions are some of the simplest things in programming. Wanna check if an age is teenage? Check to see if the age is greater than 12 (or >= 13) and less than 20 (or <= 19). You might wanna take the age mod 100 though if you want 115 or something to be considered a teenager.

Bitwise Operations

Logic gates act on indivudal booleans, true or false. A number in binary is just a sequence of true/false. So what if we take numbers of the same size in binary and then perform a logic operation on each of their bits? It sounds silly, but it's actually pretty useful somehow. It's called a bitwise operation. Although there are more bitwise operations than logic gates, like different kinds of shifts. To be a bitwise operation, they just have to do something per bit. Let's take 2 numbers, 20 and 13, and do bitwise AND, OR, and XOR on them, as well as NOT on them individually.


10100: 20
01101: 13 (equivalently 1101, but add the extra 0 so they have the same # of digits ig)

AND:
10100
01101
=====
00100 (4)

OR:
10100
01101
=====
11101 (29)

XOR:
10100
01101
=====
11001 (25)

NOT 20:
10100
=====
01011 (11)

NOT 13:
01101
=====
10010 (18)

Hopefully you can see how each bit came to be. If you're viewing this page in a browser and are interested in the numbers that you can get from doing this, go to inspect element and then to the console menu. There you can get a javascript repl or something you can punch in numbers and operators, like: '20 & 13', '20 | 13', '20 ^ 13' for bitwise and, or, xor respectively. Use ~ to do bitwise not; javascript does it on signed numbers, though, so you'll only really get the negative version of that number, minus one, and not what I got (idk if I'm doing it right or not). You just have to type it in and then you should see the result appear; if not, put it all inside a console.log function and then hit enter.

Shifts/rotations

What happens if you just shift the bits around? Move them all to the left or right? That seems easy enough, but you have to know what to do with bits that are shifted out, as well as what you wanna do with the sign bit in a signed number. The different types of shifts come from different approaches to it.

Logical shift

Probably the simplest; shift all the bits, discarding them if they get shifted off the number. Zeroes come in on the opposite direction to replace the bits that get shifted off.

1001010 (74) after logical shift RIGHT =
0100101 (37)

0011101 (29) after logical shift LEFT =
0111010 (58)

Because it doesn't handle the sign bit specially, it's mostly useful for unsigned numbers. For signed numbers, try the arithmetic shift, although note that a left logical shift is identical to a left logical shift:

Arithmetic shift

You shift all the bits, discarding all bits that get shifted off the number. When shifting left, zeroes are shifted in on the right (it's identical to a left logical shift), but when shifting right, the value of the sign bit is shifted in on the left to preserve the number's sign.

10110111 (-73) after arithmetic shift RIGHT =
11011011 (-37)

01101010 (106) after arithmetic shift RIGHT =
00110101 (53)

00101000 (40)  after arithmetic shift RIGHT TWICE =
00001010 (10)

There are a few things to note in general for these shifts. First, a right shift by n bits is equal to a floored division of the number by 2ⁿ. A left shift by n bits is equal to multiplying the number by 2ⁿ. Because bitwise operations are usually easier for a processor to do than math, any decent compiler or something should use bit shifting to optimize multiplication/division with powers of 2. Programming languages that implement shifts might also not have separate symbols for logical and arithmetic shifts, or it might only have them for a right shift since the left logical/arithmetic shifts are identical.

Circular shift

This is the 'rotation' part, where the bits that are shifted off actually just "wrap around" back on the other side. A bitwise rotation, like the shifts above, must also be left/right. The plain circular shift does the simplest thing:

1101000 after circular shift LEFT =
1010001

1001001 after circular shift RIGHT =
1100100

There's also circular shift with carry: the bit that is shifted in is the carry bit, and the bit that is shifted out becomes the carry bit. But idk much about it.

The use of all this!

Imagine there's an array of pairs of numbers and one lone number. It's in any order, and all numbers appear twice except for the lone one. How can you find what the lone number is? A naive implementation might be to iterate over it and, for each number, iterate over the rest of it and see if it appears again:
~~~

local arr = {5, 1, 6, 7, 1, 6, 5}
    --7 is the lone number
local function findlonely(arr)
 for i = 1, #arr do
  local lonely = true
  for j = i+1, #arr do
   if arr[i] == arr[j] then
    lonely = false
   end
  end
  if lonely then
   return arr[i]
  end
 end
end

print(findlonely(arr))

~Output:
7
~~~
And it sort of works. An advantage to it is that you get to find the index of the lonely number, like where it is in the array. But a disadvantage is that it's pretty inefficient! For each number, in the array, it has to search pretty the whole rest of the array. But an obscure use of bitwise XOR can do this for us probably faster:
~~~

local bit = require("bit") --bitwise operator functions in lua

local arr = {5, 1, 6, 7, 1, 6, 5}
    --exact same as above
local function findlonely(arr)
    return bit.bxor(unpack(arr))
end

print(findlonely(arr))

~Output:
7
~~~
bit.bxor is the bitwise XOR function (in lua; other languages use the ^ operator). It can take any number of arguments and takes the bitwise XOR on all of them (unpack is just a function that takes a table and returns the table as though it were just its contents separated by commas; the array portion of it, anyways), so calling it with the array is like saying "return 5 XOR 1 XOR 6 XOR 7 XOR 1 XOR 6 XOR 5". But how does that find the lonely number? Well, any number xorred with itself is just 0. Why? Well remember that XOR is true only if its operands are different; if doing bitwise XOR on identical numbers, each of the bits being xorred with each other will be the same, so the result will have 0 in all its bits. In assembly, xorring a register with itself to set it to zero is usually faster than moving 0 into the register. Also, any number xorred with 0 is just that number; all set bits in the number will be xorred with the 0 bit from 0, making the bit 1, while all unset bits in the number will be xorred with 0, making the bit 0. XOR is also associative and commutative, so the numbers can be in any order.

Outside of that, bitwise stuff is still really useful. Mostly in lower level stuff, tho. Like what if you wanna make an emulator? If you emulate a CPU, you'll probably want to emulate the flags, too, which are individual bits denoting the state of something, like the result of a comparison or the sign of the previous operation's result idk. Say there's 8 different flags that need to be toggled indivudally. You could use an array of 8 numbers to represent it, and just switch each number between 0 and 1 as needed; but this is a waste of memory! Each "bit" is now just an array of bits in of itself, and each number can technically range from 0 to 255 or even 0 to 2³²-1 depending on the implementation, but only 0 and 1 are actually used. A simple char is already an array of 8 bits, so just one of them should be able to represent the flags. The trouble comes down to manipulating the indivdual bits in it; it's not as easy as just indexing an array. But this is where bitwise operators come into play! Or maybe in the emulator flag example, you can use C bitfields. But bitwise operators are still useful:

Extracting n-th bit: you can do this by right shifting (doesn't matter whether it's arithmetic or logical) until the desired bit is the 1s place, and then bitwise anding with 1. The bitwise and will clear out everything that isn't in the ones place, so you'll be left with 1 if the bit is set, or 0 if the bit isn't set. This can be as simple as: "bit = (a >> n) & 1" (from this SO post). In lua, this might look like this:
~~~
local bit = require("bit") local function getbit(num, n) return bit.band(bit.rshift(num, n), 1) end print(getbit(0b0010, 1))--note that its like 0 indexed print(getbit(0b0010, 0)) print(getbit(52, 4))~Output:
1 0 1
~~~
Setting n-th bit: this can be done by left shifting 1 (remember it's 0000001 in binary, with however many 0s to be the size of the number) until it's in the desired place, and then bitwise oring that with the number. This might be like: "x |= (1<<n)". Remember that numbers are usually passed by value or whatever, so you're not really just setting the bit in a number; you're making a copy of the number and setting its n-th bit to 1, but you can then set the original number to that number if you want. I don't know if that's worth noting, though (in C maybe you could get around it by using addresses and stuff to make it more like an actual array). Here it is in lua:
~~~
local bit = require("bit") local function setbit(num, n) return bit.bor(num, bit.lshift(1, n)) end print(setbit(0, 0)) print(setbit(0b0111, 3)) print(setbit(70, 8))~Output:
1 15 326
~~~
* For toggling the n-th bit: instead of oring, use xor instead. Xoring anything with 1 is equivalent to toggling it
* For unsetting the n-th bit: after left shifting the 1, take the bitwise NOT of it. Then use bitwise AND instead of or. This works because the bit you wanna unset will become the only 0 bit. Everything else will be 1, which when bitwise anded with the number whose bit you wanna toggle, will preserve the rest of the number. Btw, anything bitwise anded with 1 is just that number.

Other resources

Bit hacks cheat sheet: setting/unsetting/toggling n-th bit, testing n-th bit, etc
Bit twiddling hacks: LOTS of stuff