Bitshifting to the right divides, but why?

VerticallyBehind

New member
Joined
Nov 18, 2021
Messages
2
So take the number 4200 for instance, this can be any integer I guess, but let's use that one.
Say I bitshift the value to the right by 1, it then divides the value by 2.
If I were to bitshift the value 4200 to the right by 2, then it would divide it by 4.
If I were to bitshift the value 4200 to the right by 3, then it would divide it by 8.

I understand that it has something to do with the power of 2 and the binary system and the way I look at it is like so

Multiply 2 with the index at the power of 2 table
8 4 2 1


Let's say I wanted to bitshift by 3, I would then take what's on the 3rd index of the table which is the value 4, going from right to left, and multiply it by 2. hence why bitshifting to the right by 3 is the same as dividing by 8.

I don't understand why though, and I don't feel like that would be a good answer if I were to face this on a test. Where the question is.. "Why does it multiply by 8 if you bitshift the value to the right by 3"
 

Jomo

Elite Member
Joined
Dec 30, 2014
Messages
11,486
Can you give an exact example of what you are saying? What does bit shift to the right by 2, 4, 8,...?
 

VerticallyBehind

New member
Joined
Nov 18, 2021
Messages
2
Can you give an exact example of what you are saying? What does bit shift to the right by 2, 4, 8,...?
Take the number 84 in base 2
0101 0100

If I bitshift that to the right by 1 it turns into
0010 1010

Essentially shifting every bit to the right by 1. Resulting the value to be divided by 2 (the value 42).
If I were to shift it to the right by 2, it would turn into the value 21 (divided by 4)

And bitshifting to the right by 3 would divide it by 8.

Why is it that everytime I increment the bitshift value, it increments by base 2.
 

blamocur

Full Member
Joined
Oct 30, 2021
Messages
586
So take the number 4200 for instance, this can be any integer I guess, but let's use that one.
Say I bitshift the value to the right by 1, it then divides the value by 2.
If I were to bitshift the value 4200 to the right by 2, then it would divide it by 4.
If I were to bitshift the value 4200 to the right by 3, then it would divide it by 8.

I understand that it has something to do with the power of 2 and the binary system and the way I look at it is like so

Multiply 2 with the index at the power of 2 table
8 4 2 1


Let's say I wanted to bitshift by 3, I would then take what's on the 3rd index of the table which is the value 4, going from right to left, and multiply it by 2. hence why bitshifting to the right by 3 is the same as dividing by 8.

I don't understand why though, and I don't feel like that would be a good answer if I were to face this on a test. Where the question is.. "Why does it multiply by 8 if you bitshift the value to the right by 3"
BTW, Your table needs 0-based indexing because [imath]1 = 2^0\, 2=2^1, 4=2^2, 8=2^3[/imath]. I.e., 1 is 0th element, 2 is 1st, 4 is 2nd and 8 is 3rd. This way to bitshift by 3 you have to divide (in the case of the right shift) or multiply (in the case of the left shift) by 8.

As for why numbers get divided by two when their binary representation is shifted to the right by 1 position, it follows from the definition of the binary representation. Just to keep it simple, consider a 3-bit number [imath]x[/imath] with binary digits [imath]a_2, a_1, a_0[/imath]. By definition [imath]x=a_2 2^2 + a_1 2^1 + a_0 2^0 = 4a_2 + 2a_1 + a_0[/imath]. When you integer-divide it by two you get [imath]y= x/2 = 2a_2 + a_1= a_2 2^1 + a_1 2^0[/imath], which corresponds to the binary notation with digits [imath]a_2,a_1[/imath], i.e. shifted to the right by 2.
 

Cubist

Senior Member
Joined
Oct 29, 2019
Messages
1,215
It might help you to remember the words "place value" which you were probably taught a very long time ago and perhaps forgot. It was a big step forwards in the notation of writing down numbers when "0" was added to the lexicon along with the idea that the position of a digit affects its meaning/ value. With binary notation you have a different base to decimal, and so the place value is different.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
7,112
A bit string is an ordered sequence of one or more zeroes or ones. Bit strings can be interpreted as integers expressed in binary numerals. (It is traditional but sloppy nomenclature that calls “binary numerals” ”binary numbers.”) Bit shifting is an operation defined on bit strings.

Shifting a bit string one place to the left adds a zero to the end of the string. When interpreted as a number expressed as a decimal numeral, the resulting number is 2 times the original number.

Shifting a bit string one place to the right removes the final element of the string. When interpreted as a number expressed as a decimal numeral, the resulting number is one half the original number IF and ONLY IF the original number is an even number.

Consider the string 11. If that is interpreted as a binary numeral, it represents the number three. If we bit shift one place to the left, we get 110. If that is interpreted as a binary numeral, it represents the number six, which is two times three. If we bit shift one place to the right, we get 1. If that is interpreted as a binary numeral, it represents the number one, which is NOT one half of three.

I really do not know if your question is about binary numerals or bit strings. Your examples use decimal numerals.

Do you understand binary numerals?
 

Cubist

Senior Member
Joined
Oct 29, 2019
Messages
1,215
Just an extra thing to consider after reading @JeffM 's post

A number written in base 2 could be given a point (analogous to a decimal point). In this scenario, the number 11 (shown in base 2) would be shifted right to become 1.1 (base 2) and that value written in decimal is 2^0 + 2^-1 = 1.5 which is exactly half of 3. @JeffM obviously describes the more common situation where the binary representation has no "binary point", and then "underflow" can occur. Of course "overflow" might also occur when shifting left if your representation (perhaps within a CPU register) has a limited number of bits available.
 

JeffM

Elite Member
Joined
Sep 14, 2012
Messages
7,112
@Cubist

You are of course correct. I left out of consideration any radix point, nor did I consider that in practice most bit strings have a fixed length.

My concern was to get the OP to elucidate what he understands.
 
Top