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.