Yes, Ethereum is the world’s computer, though probably the most expensive one. Since storage is the largest gas-consuming operation, occasionally it is reasonable to dig down to the level of bits. Same as Assembly coder would do while programming firmware of a microchip. This will allow to get more control over your data and ultimately reduce transaction cost.
Smart contract language Solidity supports basic bitwise operations, though some of them are missing (like left/right shift). Luckily there’s arithmetic equivalents.
The purpose of the article is to give you fundamental primitives for bit manipulation which can be used in more complex constructions.
All bitwise operations are executed bit by bit, same way you would compare elements of two different arrays at the same index. Note: 0 and 1 have the same meaning as false and true and vice-versa.
For simplicity I’ll gonna use bytes1 data type (equal to byte), though same will apply to larger datatypes. Lets use same a and b variables for all examples:
We use hex representation to initialize them in Solidity:
bytes1 a = 0xb5; // [10110101]
bytes1 b = 0x56; // [01010110]AND
Both bits must be 1s to result in true.
(Inputs have white background and result is highlighted by yellow one)
a & b; // Result: 0x14 [00010100]OR
At least one of the bits have to be 1 (true).
a | b; // Result: 0xf7 [11110111]XOR
Can be described as a difference between two inputs. One of the inputs have to be 1 and the other one must be 0 to result in true. Simply a[i] != b[i]. XOR operation often applied in cryptographic algorithms.
a ^ b; // Result: 0xe3 [11100011]Interesting property is that if you want to know what was the value of original b, just XOR result with a. In one sense a is the key to unlock b.
0xe3 ^ a; // Result: 0x56 == b [01010110]Negation
Negation, an inversion operation usually associated with the character “~”. Zero becomes one, one becomes zero.
Solidity doesn’t have support for negate operation. Luckily negation is the same as to XOR input with all 1s.
a ^ 0xff; // Result: 0x4a [01001010]Bit Shift
Since there’s no bit shift functionality in Solidity we can use arithmetics to do the same thing. I’m going to use decimal number to show the concept.
What shift basically means is that I want to move some digits N positions to the left or to the right.
Take for example 1230 (zeros prefixed for illustration purposes):
00001230If we want to shift this number to the left by 3 positions we expect result to be:
01230000Which in other words just means to multiply by 10, 3 times (10³).
And if we want to shift to the right by 4 positions it’s the same as to divide 4 times by 10 (10⁴):
00000123Same applies to binary, though instead of 10 digits (0 – 9) there’s only 2 (0, 1). Henceforth we multiply or divide by 2.
Note: If you need to manipulate more than bytes32 at a time, slight modifications are necessary to use shift operations.
Left Shift
Shift a 3 bits left
var n = 3;
var aInt = uint8(a); // Converting bytes1 into 8 bit integer
var shifted = aInt * 2 ** n;
bytes1(shifted); // Back to bytes. Result: 0xa8 [10101000]Right Shift
Shift a 2 bits right
var n = 2;
var aInt = uint8(a); // Converting bytes1 into 8 bit integer
var shifted = aInt / 2 ** n;
bytes1(shifted); // Back to bytes. Result: 0x2d [00101101]Get First N Bits
We can create a mask of needed count of 1s in order to filter the part we’re looking for by applying AND operation. For first 5 bits:
var n = 5;
var nOnes = bytes1(2 ** n - 1); // Creates 5 1s
var mask = shiftLeft(nOnes, 8 - n); // Shift left by 3 positions
a & mask; // Result: 0xb0 [10110000]Note: var nOnes = 0xff; will work the same way
Get Last N Bits
There’s arithmetic way to get last N bits. We can achieve that using modulo. For example if want to get last 2 digits from 10345, we can easily do it by dividing by 100 (10²) and getting remainder.
10345 % 10 ** 2 = 45Same with binary, though this time we’re getting modulo of multiples of 2. For example to get last 5 bits:
var n = 5;
var lastBits = uint8(a) % 2 ** n;
bytes1(lastBits); // Result: 0x15 [00010101]Data Packing Use Case
Lets say you have two 4-bit values c and d that you want to pack into one 8-bit value.
Here’s how you can do it:
bytes1 c = 0x0d;
bytes1 d = 0x07;
var result = shiftLeft(c, 4) | d; // 0xd7 [11010111]c takes first 4 bits and d takes remaining 4 bits, can be other way around.
Primitives Source Code
contract BitsAndPieces {
function and(bytes1 a, bytes1 b) returns (bytes1) {
return a & b;
}
function or(bytes1 a, bytes1 b) returns (bytes1) {
return a | b;
}
function xor(bytes1 a, bytes1 b) returns (bytes1) {
return a ^ b;
}
function negate(bytes1 a) returns (bytes1) {
return a ^ allOnes();
}
function shiftLeft(bytes1 a, uint8 n) returns (bytes1) {
var shifted = uint8(a) * 2 ** n;
return bytes1(shifted);
}
function shiftRight(bytes1 a, uint8 n) returns (bytes1) {
var shifted = uint8(a) / 2 ** n;
return bytes1(shifted);
}
function getFirstN(bytes1 a, uint8 n) returns (bytes1) {
var nOnes = bytes1(2 ** n - 1);
var mask = shiftLeft(nOnes, 8 - n); // Total 8 bits
return a & mask;
}
function getLastN(bytes1 a, uint8 n) returns (bytes1) {
var lastN = uint8(a) % 2 ** n;
return bytes1(lastN);
}
// Sets all bits to 1
function allOnes() returns (bytes1) {
return bytes1(-1); // 0 - 1, since data type is unsigned, this results in all 1s.
}
// Get bit value at position
function getBit(bytes1 a, uint8 n) returns (bool) {
return a & shiftLeft(0x01, n) != 0;
}
// Set bit value at position
function setBit(bytes1 a, uint8 n) returns (bytes1) {
return a | shiftLeft(0x01, n);
}
// Set the bit into state "false"
function clearBit(bytes1 a, uint8 n) returns (bytes1) {
bytes1 mask = negate(shiftLeft(0x01, n));
return a & mask;
}
}