# Bitwise Operations and Bit Manipulation in Solidity, Ethereum

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 **1**s 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 **1**s.

`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):

`00001230`

If we want to shift this number to the left by **3** positions we expect result to be:

`01230000`

Which 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⁴**):

`00000123`

Same 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

bytes32at 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 **1**s 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 = 45`

Same 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;

}

}