Working with binary numbers

In a programming puzzle, I (surprisingly) noticed I've never really worked with binary strings in programming before. As you may expect, this is such a basic operation that programming languages will have some useful default operations on binary strings.

In Python, converting a decimal to binary representation can be done with a default function:

>>> bin(5)
'0b101'

When an integer in decimals is required, you can actually provide the base of the input:

>>> int(bin(5), base=2)
5

I'm trying to learn Lua at the moment. Lua's tonumber works the same, although Lua doesn't seem to have a default function for converting decimals to binary:

> bin = '101'
> tonumber(bin, 2)
5

Bitwise operations

Lua does have a library for bitwise operations

Languages typically have logical operations on bits, such as a bitwise OR or XOR. These are the basic functions that are implemented in physical circuits.

However, I wasn't familiar with the use of the bit shift operations (both to the left or right) A left shift shifts the existing bits to the left and fills the vacant places with zeros. A right shift shifts the bits to the right, annulling those that "fall off at the right side". In Python, we have:

>>> 5 << 2
20

The binary representation of 5 is 101. Shifting two bits to the left gives 10100, which is 20 is decimal. Turns out that x << y is equivalent to x * 2**y. When shifting to the right we instead go from 101 to 1:

>>> 5 >> 2
1

So this operation is equivalent to x // 2**y, where // indicates the amount of whole divisions. E.g. 5//2 will yield 2.

TODO: what are the main applications of this shift operation? Why is it so useful?

In python, the tilde operator ~ is a bitwise negation that flips each bit. However, the bit representation of an integer encompasses multiple bits, of which one is reserved for the sign. The results may be a bit surprising. When reserving the first bit for the sign:

~0 -> ~00000000 -> 11111111 -> -1

~5 -> ~00000101-->11111010 -> -6

The pattern is consistent: for an integer i the bitwise negation results in -i -1.