Bitwise operations
It is a well-known fact that the fundamental element of memory is the bit: the smallest memory cell that can take only binary values. All data is ultimately organized in bytes, which are nothing more than packets of 8 bits. Each type of data therefore has its own binary representation by which it is actually stored in memory. Some of you may have read my previous article What are Hex Colors? in which we introduced binary and hexadecimal numbers, we will use binary numbers in this article, so I hope to find you pretty confident about this topic. There are a number of operations typical of the binary number system, which is precisely why we speak of Boolean algebra. Just because of its low-level nature, the operations on the individual bits are extremely fast and allow very interesting things to be done.
Logical operators
The first class of bitwise operators we are going to look at are the ones also known as logical operators. Most of you will already know them, they are very important operators in computer science and are used to write conditional statements, we are talking about AND, OR and NOT.
In case you are not familiar with these logical operators I suggest you read this article about them, otherwise here is a small recap:
The easiest way to introduce these operations is to think of Boolean variables as true and false, let’s say for example that a AND b is true if and only if both a and b are true, similarly a OR b is true if at least one of the two variables is true, finally NOT a is true if a is false and is false if a is true.
To these operators we shall add then the XOR. The operation a XOR b is true if one and only one of the two variables is true. We do not often mention the XOR as a logical operator because it is actually a derived operator, in fact a XOR b is equivalent to (a AND NOT b) OR (NOT a AND b). When it comes to bitwise operations however, the XOR is widely used, which is why many languages support it natively without the need to write the above formula.
In a more general sense, however, it is simpler to consider Boolean variables not as true and false but as 1 and 0; moreover, most data are not single-bit but multi-bit, so the idea is to perform the operation on all the bits that make up the given data. Let us give a couple examples.
Simple case: 1 AND 0 = 0, is the same as saying True AND False = False.
Let us instead take the numbers 6 and 3, convert them to binary and get 110 and 011, how much is 6 AND 3? The answer is 2, in fact 1 AND 0 = 0, 1 AND 1 = 1, 0 AND 1 = 0 so 110 AND 011 = 010 which corresponds to 2.
N.B. Usually programming languages distinguish between logical operators and bitwise operators, let us make an example. If you try to write on a python shell a or b, this will return a if a is a not null or empty value and b otherwise, on the other hand a or b will return b if b is a not null or empty value and a otherwise, not a will instead perform an implicit conversion of a to a boolean, meaning that it is equivalent tonot bool(a) and will therefore return a boolean, if we want to perform a bitwise operation instead we will use the symbols & for AND, |for OR, ^for XOR e ~for NOT.
Shift operators
Shift operators, as the name implies, perform a shift of their bits, the left shift to the left and the right shift to the right. The operator takes two inputs, the first operand is the object we want to manipulate, while the second operand specifies by how many positions we want to shift the bits of the first operand. Bits that are shifted out of machine bounds are lost, while bits that are vacated are set to 0.
The value of shift operators is undefined if the value of the second operand is negative, so a left shift of a negative number of positions does not necessarily result in a right shift.
Doing a little math, one realizes that by shifting the bits, for each shift to the left the value is multiplied by two, and for each shift value to the right it is divided by two, this again unless the above effects are taken into account.
Interacting with data with bitwise operations
All data are saved as aggregations of bits, nevertheless when we talk about bitwise operations we are always talking about numbers, this is because the conversion to integer is always an intermediate step.
Suppose we are dealing with a character: in python there is the ord()function that accepts a character and returns its numeric value, for example running the ord("H") command will result in the number 72, wanting to convert the string “Hello world”, we will make the conversion for each individual letter and get [72, 101, 108, 111, 32, 119, 111, 114, 108, 100].
Similarly, we can use struct.pack() to convert a float into an object of type bytes, which is nothing more than a compressed representation of a list of integers. For example, let us try to convert the number 3.14, the command list(struct.pack('!f',3.14)) returns [64, 72, 245, 195].
Binary numbers after all are nothing but integers, that is why we always have such a direct correlation and that is why we always talk about integers and not other types of data, in any case a conversion to integers is always possible.
A note on encoding types for negative numbers
As we know, numbers can be either positive or negative. To represent negative numbers there are basically two techniques, the first is the representation in sign and modulus, in which the first bit is deputed store the sign, if it is 0 it is positive, if it is 1 it is negative. The other bits, meanwhile, represent the modulus.
Example:
Another strategy is the 2’s complement strategy where the first bit is again deputed to represent the sign, this time however the idea is based on the property whereby a + NOT a = 1, hence NOT a = 1 — a this implies that if a = 0, then a = -1, but the result of NOT 0 is the number with all bits at 1.
Suppose we are working in 8 bits, then with the first strategy the number 11111111 is equal to -127 i.e. the lowest representable number, but with the second strategy it is equal to -1. To make it clear, to calculate the value of a number, with 2’s complement we consider the first power to be negative and all others to be positive.
Example:
We therefore understand that depending on the type of encoding we may have different results when we go to do bitwise operations, especially with NOT operator.
It often happens that we want to work in “pure” binary, without sign. In order to do this, special data types can be used. Some languages natively support unsigned numbers, for others it is necessary to import libraries, but in any case it is a feasible way.
A more purist solution instead may be to use instead of NOT the XOR with the number having all bits set to 1, be careful though because if you use a number with a different number of bits the excess ones are set to 1 resulting in a larger number.
An implementation of this in python could be: NOTx = x^((2**x.bit_length())-1).
Speed of execution
One of the first things said was that bitwise operations are very fast in execution, and can therefore make our code more efficient. Here is an example that exploits a property of binary numbers to check whether a number is even or odd:
Which produces as result:
Check: True
Method 1: 0.8872146606445312
Method 2: 1.1341464519500732Conclusions
The field of bitwise operations is extremely interesting and brings us closer to a more profound understanding of how a computer works; they allow us to perform actions in manners we would not normally think of.
Bitwise operations are used in many fields, especially in cryptography, but they are expendable in any field for optimization reasons because of their high speed.
