What is the purpose of bit shifting?

Question

I came across the below lines in code

unsigned char A = 0xB9;
unsigned char B = 0x91;
unsigned char C = A << 3; // shift bits in A three bits to the left.
unsigned char D = B >> 2; // shift bits in B two bits to the right.

I know that it's bit-shifting, but what purpose does it serve and when should one use it?

If it does not mean anything to you, it has no purpose. Just ignore the code. — leppie, Jun 17 '12 at 14:57
This question is too broad; there is no answer. What is the purpose of addition? It's an operation. — Dave Hillier, Jun 17 '12 at 14:57
Yes, it doesn't mean to me, but i think that i should know about it! — Kingfisher Phuoc, Jun 17 '12 at 15:10
In my humble opinion this is a valid question. Please close it but with some other more relevant reason than pronouncing it as "not a real question". Regards, — Junaid Qadir Shekhanzai, Apr 16 '14 at 18:38
thankfully, someone squeezed in an answer before it got closed — anton1980, Oct 08 '15 at 20:06

score 22 · Accepted Answer · edited Aug 08 '22 at 08:40

The primary use is when you have some part of a larger item defined in terms of specific bits.

For an obvious example, consider a 32-bit number holding a color -- 8-bits each for red, green, and blue, and (possibly) the other 8 bits for alpha (signifying how transparent this color/pixel should be). In hexadecimal, the digits would look like:

AARRGGBB

(i.e., two digits, or 8 bits) for each component).

We can take such a thing and break it into components something like:

red = color & 0xff;
green = (color >> 8) & 0xff;
blue = (color >> 16) & 0xff;
alpha = (color >> 24) & 0xff;

Conversely, we can put components together:

color = (alpha << 24) | (blue << 16) | (green << 8) | red;

You also typically end up doing bit-twiddling like this when dealing with hardware. For example, you might have a 16-bit register that dedicates 5 bits to one thing, 2 more bits to something else, 6 bits to a third, and so on. When/if you want to change one of those, you do about like the color example, above: isolate the bits that represent one field, modify as needed, then put them back together with the other bits.

Another (quite unrelated) application is in things like hashing. Here we don't typically have fields as such, but we want some bytes of input to produce a single output, with all the bits of the output affected to at least some degree by the bytes of the input. To accomplish that, most end up shifting bits so each byte of input has at least some chance of affecting different parts of the result.

I'd add that although quite a bit of older code uses bit shifts to optimize multiplication or division by powers of 2, this is usually a waste of time with modern hardware and compilers. You will see it in existing code, and should understand what it's trying to accomplish -- but don't try to emulate its example.

Some people say that using bit-shifting is little bit faster than a normal way? Is this right? — Kingfisher Phuoc, Jun 17 '12 at 15:09
@Kingfisher: a normal way of what? If you mean bit-shifting vs. multiplication/division, yes a bit-shift instruction may be faster than a mul/div instruction -- but when that's so, most compilers are *quite* capable of carrying out that optimization for you. — Jerry Coffin, Jun 17 '12 at 15:11
Am I reading it wrong, or is the first code sample (as written) actually for AABBGGRR not AARRGGBB? — Monte Hurd, Feb 24 '13 at 04:22
@MonteHurd: I don't think there's enough there to say it's colors at all. — Jerry Coffin, Feb 24 '13 at 04:49
Exactly - if someone were using the example to test their understanding of bit-shifting (regardless of color, using "a, "r", "g" and "b" only for relative byte location) the code as written works for AABBGGRR, not AARRGGBB. — Monte Hurd, Feb 24 '13 at 05:01

score 10 · Answer 2 · edited Apr 24 '22 at 23:34

10

An example is a (monochrome) bitmap, where the pixels are represented by a single bit each. Suppose you have a circle

........
...oo...
..O..O..
.O....O.
.O....O.
..O..O..
...oo...
........

where a . is represented by a 0 bit and a O by an 1 bit, so the second line is represented by binary 00011000, or decimal 24. Now if you want to move the circle 1 pixel to the right, what you do is shift the bits in its representation 1 bit to the right.

........
....oo..
...O..O.
..O....O
..O....O
...O..O.
....oo..
........

So the second line is now 00001100 after shifting, (or decimal 12).

edited Apr 24 '22 at 23:34

Peter Mortensen

30,738
21
105
131

answered Jun 17 '12 at 15:00

Mr Lister

45,515
15
108
150

4

+1 for monochromatic sprite scrolling. Now we are really showing our age. – StuartLC Jun 17 '12 at 15:02
Never thought about this. This must've been popular way back when. – chris Jun 17 '12 at 15:04

StuartLC · Answer 3 · 2022-08-08T07:57:25.957

5

Bit shifting has several purposes

Multiplication or division by powers of two
Checking whether the most or least significant bit is set (MSB or LSB) is set by looking for overflow [or underflow] after a shift left [right].
~~Weak forms of encryption~~. No.

edited Aug 08 '22 at 07:57

answered Jun 17 '12 at 14:55

StuartLC

104,537
17
209
285

4

Weak forms of encryption, really? – Hasturkun Jun 17 '12 at 14:56
@Hasturkun: 99% of first-time attempts at writing a cipher is weaker than XOR. – leppie Jun 17 '12 at 14:58
@leppie: It's misleading because bit shifting is also used in all common strong encryption algorithms, such as DES and AES. – MSalters Jun 18 '12 at 09:00

mathematician1975 · Answer 4 · 2012-06-17T15:36:02.563

0

One use is division or multiplication by integer powers of 2.

edited Jun 17 '12 at 15:36

answered Jun 17 '12 at 14:53

mathematician1975

21,161
6
59
101

Fast? As opposed to regular arithmetics or what? – Luchian Grigore Jun 17 '12 at 15:08
@LuchianGrigore When I was taught C++ in my first job my mentor told me that it was actually faster than writing the code as explicit division by 2. At the time I had no reason to disbelieve him. If this is in fact not true then I humbly stand corrected. – mathematician1975 Jun 17 '12 at 15:12
In that case I will recommend to my former boss that his salary be reduced immediately. – mathematician1975 Jun 17 '12 at 15:32
See this - http://stackoverflow.com/questions/6357038/is-multiplication-and-division-using-shift-operators-in-c-actually-faster – Luchian Grigore Jun 17 '12 at 15:35
@LuchianGrigore Thanks for that link. I had simply always assumed that it was faster. I have edited the answer now anyway to remove the implication that it is faster. – mathematician1975 Jun 17 '12 at 15:38
@LuchianGrigore I know for a fact that an integer division (on an Intel i586 at least) takes longer than a bit shift. But the issue is that in situations where you can choose between bit shifting and division, it's usually implied that you are dividing or shifting by a _constant_. And if you have constants, the compiler starts optimising and all bets are off. – Mr Lister Jun 17 '12 at 15:50
@MrLister that may be, but it's likely that a division is optimized to a shift anyway (if it can be). – Luchian Grigore Jun 17 '12 at 15:54

score 0 · Answer 5 · answered Jun 17 '12 at 14:54

0

Bit-shifting or Bit patterns are used for compressing files. Some use it for encryption too.

answered Jun 17 '12 at 14:54

craig1231

3,769
4
31
34

score 0 · Answer 6 · edited Apr 24 '22 at 23:34

0

There are a lot of uses for shifting. More than realistically can be explained here. A good example would be shifting values into the right position when assembling code. Also a left shift of 1 is the same as multiplying a value by 2, only much faster. Likewise a right shift is the same as dividing by 2.

edited Apr 24 '22 at 23:34

Peter Mortensen

30,738
21
105
131

answered Jun 17 '12 at 14:55

timkd127

71
1
6

What is the purpose of bit shifting?

6 Answers6

Linked