Can someone explain why ">> 2" means "dividing by 4" in C codes?

Question

I know and understand the result.

For instance:

<br> 7 (decimal) = 00000111 (binary) <br> and 7 >> 2 = 00000001 (binary) <br> 00000001 (binary) is same as 7 / 4 = 1 <br> So 7 >> 2 = 7 / 4 <br> <br> 

But I would like to know how this logic is created.
Can anyone clarify this logic?
(Maybe it just surfaced in the head of a genius?)

And are there any other similar logic?

Answer 1

It did not "pop up" in the head of a genius. A right shift of binary numbers would divide the number by 2, and a left shift of numbers would multiply it by 2. This is because 10 is a binary number 2. Multiplying a number by 10 (whether binary, decimal or hexadecimal) adds 0 to the number (which actually moves to the left). Similarly, dividing by 10 (or 2) removes the binary digit from the number (actually shifting to the right). This is how logic really works.

In the computer world, there are many such bit-twiddlery (a word that I came up with a minute ago).

http://graphics.stanford.edu/~seander/bithacks.html Here's a start.

This is my favorite book: http://www.amazon.com/Hackers-Delight-Edition-Henry-Warren/dp/0321842685/ref=dp_ob_image_bk bit-tiddlery.

Answer 2

I think you are confused by "2" in:

 7 >> 2 

and think that he should divide by 2.

"2" here means shifting the number ( "7" in this case) "2" bit position to the right.

The shift of the bit position of the number "1" to the right will have the effect of dividing by 2:

 8 >> 1 = 4 // In binary: (00001000) >> 1 = (00000100) 

and shifting the bit positions of the number "2" to the right will have the effect of dividing by 4:

 8 >> 2 = 2 // In binary: (00001000) >> 2 = (00000010) 

Answer 3

In fact, this is defined in the C standard.

From section 6.5.7:

Result E1 → E2 are the right positions of E2 in E1. [...] the significance of the result is an integral part of the factor E1 / 2 ^E2

In most architectures, x >> 2 is only x / 4 for non-negative numbers. For negative numbers, it is usually rounded in the opposite direction.

Compilers have always been able to optimize x / 4 at x >> 2 . This method is called force reduction, and even the oldest compilers can do this. Thus, there is no use to writing x / 4 as x >> 2 .

Answer 4

It is inherent in the binary system used on a computer.

similar logic --- left shift "n" means multiplication by 2 ^ n.

Answer 5

they do this because switching is more efficient than actual division. you just move all the numbers left or right, logically multiplying / dividing by 2 per shift

If you're wondering why 7/4 = 1, this is because the rest of the result (3/4) is truncated, so this is a link.

Answer 6

Only my two cents: I did not see the mention that the right shift does not always produce the same results as dividing by 2. Since the right shift is rounded to negative infinity and rounds the rounded numbers to zero, some values ​​(for example, -1 in two additions) will simply not work as expected during the split.

Answer 7

Elaboration of Aniket Inge answer :

Number: 307 ₁₀ = 100110011 ₂

How to multiply by 10 works in decimal

10 * (307 ₁₀ )

= 10 * (3 * 10 ² + 7 * 10 ⁰ )

= 3 * 10 ^{2 + 1} + 7 * 10 ^{0 + 1}

= 3 * 10 ³ + 7 * 10 ¹

= 3070 ₁₀

= 307 ₁₀ <1

Similarly, multiply by 2 in binary ,

2 * (100110011 ₂ )

= 2 * (1 * 2 ⁸ + 1 * 2 ⁵ + 1 * 2 ⁴ + 1 * 2 ¹ 1 * 2 ⁰ )

= 1 * 2 ^{8 + 1} + 1 * 2 ^{5 + 1} + 1 * 2 ^{4 + 1} + 1 * 2 ^{1 + 1} 1 * 2 ^{0 + 1}

= 1 * 2 ⁹ + 1 * 2 ⁶ + 1 * 2 ⁵ + 1 * 2 ² + 1 * 2 ¹

= 1001100110 ₂

= 100110011 ₂ <1

Answer 8

You can call it the idea of ​​a brilliant mind or just the need for a computer language.

In my opinion, a computer as a device never divides or multiplies numbers, rather, it has only the logic of adding or simply shifting bits from here to the place. You can do the work of the algorithm by instructing the computer to multiply, subtract them, but when the logic reaches the actual processing, your results will be either the result of shifting bits, or just adding bits.

You might just think that to get the result of dividing the number by 4, the computer actually shifts the bits in two places and gives the result:

 7 in 8-bit binary = 00000111 Shift Right 2 places = 00000001 // (Which is for sure equal to Decimal 1) Further examples: //-- We can divide 9 by four by Right Shifting 2 places 9 in 8-bit binary = 00001001 Shift right 2 places: 00000010 // (Which is equal to 9/4 or Decimal 2) 

A person with deep knowledge of assembly language programming can explain this with more examples. If you want to know the real meaning of all this, I think you need to learn bit level arithmetic and computer assembly language.

Answer 9

A simple way to understand why this works is to look at a familiar decimal number system, 050 is fifty, move it to the right, it will be 005, five, which is equivalent to dividing it by 10. The same thing with a left shift of 050 becomes 500, five hundred , which is equivalent to multiplying by 10.

All other number systems work the same way.