# Understanding Left and Right Bitwise shift on a 128-bit number

Artichoke101 asked this:

Lets say that I have an array of 4 32-bit integers which I use to store the 128-bit number

How can I perform left and right shift on this 128-bit number?"

My question is related to the answer Remus Rusanu gave:

void shiftl128 ( unsigned int& a, unsigned int& b, unsigned int& c, unsigned int& d, size_t k) { assert (k <= 128); if (k > 32) { a=b; b=c; c=d; d=0; shiftl128(a,b,c,d,k-32); } else { a = (a << k) | (b >> (32-k)); b = (b << k) | (c >> (32-k)); c = (c << k) | (d >> (32-k)); d = (d << k); } } void shiftr128 ( unsigned int& a, unsigned int& b, unsigned int& c, unsigned int& d, size_t k) { assert (k <= 128); if (k > 32) { d=c; c=b; b=a; a=0; shiftr128(a,b,c,d,k-32); } else { d = (c << (32-k)) | (d >> k); \ c = (b << (32-k)) | (c >> k); \ b = (a << (32-k)) | (b >> k); \ a = (a >> k); } }

Lets just focus on one shift, the left shift say. Specifically,

a = (a << k) | (b >> (32-k)); b = (b << k) | (c >> (32-k)); c = (c << k) | (d >> (32-k)); d = (d << k);

How is this left shifting the 128-bit number? I understand what bit shifting is, << shifts bits left, (8-bit number) like 00011000 left shifted 2 is 01100000. Same goes for the right shift, but to the right. Then the single "pipe" | is OR meaning any 1 in either 32-bit number will be in the result.

How is a = (a << k) | (b >> (32-k)) shifting the first part (32) of the 128-bit number correctly?

## Answers

This technique is somewhat idiomatic. Let's simplify to just a and b. We start with:

+----------+----------+ | a | b | +----------+----------+

and we want to shift left some amount to obtain:

+----------+----------+ | a : | b : | c ... +----------+----------+ |<--x-->| | ->|y |<-

So X is simply a << k. y is the k msbs of b, right-aligned in the word. You obtain that result with b >> (32-k).

So overall, you get:

a = x | y = (a << k) | (b >> (32-k))

*[Note: This approach is only valid for 1 <= k <= 31, so your code is actually incorrect.]*