I wrote this article in 2021 on Hashnode as I was wrapping my head around different spatial referencing systems. I am reposting it here to archive it. Hopefully it helps with understanding the basics that underly spatial grids like [[Bing Tiles]]
A quick reference for bitwise operators. These operators define the way that computers rearrange bits to perform calculations and represent data. Bitwise operators are supported directly by computer processors to perform calculations and store information in memory.
These operators are the basis for higher level mathematical operations. It is helpful to have an understanding of binary to understand these operations, see Binary and Hexadecimal for an introduction. Understanding the basics of bitwise operators will help you understand the way that your computer actually performs computations using collections of bits.
1. Overview
We will look at three types of bitwise operator:
Logical operators
Shifts
Rotations
2. Logical operators
AND: identifies the set bits that are shared between operands.
0010 AND 1110 = 0010
OR: identifies any set bits in either operand.
0010 OR 1110 = 1110
XOR: sets bits only if they are different between operands.
0010 XOR 1110 = 1100
NOT: Also known as the “complement,” reverses the bits in an operand.
NOT 0010 = 1101
3. Shifts
Bit shifts rearrange bits by shifting them some number of positions. Shifts remove and replace bits, in this case, we replace bits with zeros.
LEFT SHIFT: Shifts bits left by some number of positions.
Shifting bits left by 1 place:
LEFT SHIFT 1101 BY 1 = 1010
Shifting bits left by 3 places:
LEFT SHIFT 1101 BY 3 = 1000
RIGHT SHIFT: Shifts bits right by some number of positions.
Shifting bits right by 1 place:
RIGHT SHIFT 1101 BY 1 = 0110
Shifting bits right by 3 places:
RIGHT SHIFT 1101 BY 3 = 0001
4. Rotations
Rotations are similar to shifts but do not discard bits from the end of an array. They are also called “circular shifts” because they shift bits in a circle from the front to the end of a bit array.
LEFT CIRCULAR SHIFT: Performs a left shift by some number of positions and adds the shifted bits to the end of the array, rather than discarding them.
Rotating bits left by 1 place:
LEFT CIRCULAR SHIFT 1101 BY 1 = 1011
RIGHT CIRCULAR SHIFT: Performs a right shift by some number of positions and adds the shifted bits to the end of the array.
Rotating bits right by 1 place:
RIGHT CIRCULAR SHIFT 1101 BY 1 = 1110
Rotations do not remove and replace information in the same way that shifts do.
5. Endianness
For our bitwise operations to work correctly, we need to know which way bits will be processed in our computer. The way that we refer to this is “endianness,” a term that describes which position in a bit array is the starting position. This will be the position where the computer starts writing or reading when it is processing a bit array.
There are two types of endianness: “Big-endian” and “Little-endian.” In “Big-endian” systems, bits are processed starting from the smallest memory address while in “Little-endian” systems, they are processed from the largest memory address. Shifts and rotations will produce different results depending on the endianness of a system.
6. Use for mathematical operations
Why are bitwise operators important? They form the core operations that allow a computer to perform mathematical calculations on bits. To illustrate, we will use binary operators to perform an addition of two integers: 0001 and 0010 (This is 1 and 2 in decimal).
To perform an addition, we perform the following operations and test for the case where one of our operands equals zero:
1. AND
2. XOR
3. LEFT SHIFT
See the full pseudocode here.
Using our example operands, there is only one iteration needed to perform an addition.
Therefore, we can reduce the required steps to a single XOR operation:
0010 XOR 0001 = 0011
This is the same as 1 + 2 = 3 in decimal. Using a single operator is a bit of a fluke, a more complex addition would require multiple iterations. Still, recognize how we performed a mathematical operation using a binary operator. The core mathematical operations that your processor performs are constructed this way.
7. Conclusion
This is a quick reference for the basic bitwise operators. While it is almost certainly unnecessary for most people to understand bitwise operators in depth, it is worth understanding how your computer uses them to represent data and perform computations. Hopefully this helps you develop an intuitive connection between the operations performed on bits at the processor level, and the higher level the computations your computer performs.
Sources
en.wikipedia.org/wiki/Bitwise_operation
en.wikipedia.org/wiki/Endianness