除法和乘以2的幂 [英] division and multiplication by power of 2

问题描述

我在一篇论文中读到，将数字除以2的幂是一个微不足道的过程. 我在互联网上搜索了很多说明，但没有得到. 任何人都可以用简单的言语解释这实际上意味着什么.

I read in a paper that division and multiplication of a number by a power of 2 is a trivial process. I have searched a lot of internet for the explanation but doesn't get it. Can any one explain in easy words what does this actually meant to say.

推荐答案

从位操作的角度来看，这是微不足道的.乘以2等于左移1位，除法是右移.同样，乘以除以2的幂也是相同的.

It is trivial from the bit operations perspective. Multiplying by 2 is equivalent to a shift left by 1 bit, division is a right shift. similarly it is the same trivial to multiply and divide by any power of 2.

int a = 123;           // or in binary format: a = 0b01111011;

assert (a * 2) == (a << 1);   // 2 = 2^1, (a << 1) = 11110110
assert (a / 2) == (a >> 1);   // 2 = 2^1, (a >> 1) = 00111101

assert (a * 8) == (a << 3);   // 8 = 2^3, (a << 3) = 1111011000
assert (a / 8) == (a >> 3);   // 8 = 2^3, (a >> 3) = 0000001111

还要注意，a*2 = a+a和加法有时甚至比移位便宜，具体取决于硬件.

Also note that a*2 = a+a, and addition is sometimes even cheaper than shifting, depending on the hardware.

对于有符号除法，请注意，在某些语言(例如C)中，整数除法会截断为零，而算术右移(以2的补码形式在符号位的副本中移位)始终会舍入为-Infinity.例如(-5)/2 == -2，但(-5) >> 1 == -3.仍然可以通过shift +额外的操作来添加2来实现有符号除法，以添加符号位以获得截断行为. (看一下C编译器的输出.)

For signed division, beware that in some languages (such as C), integer division truncates towards zero, while arithmetic right shift (shifting in copies of the sign bit for 2's complement) always rounds towards -Infinity. e.g. (-5)/2 == -2, but (-5) >> 1 == -3. Implementing signed division by 2 can still be done with a shift + extra operations to add the sign bit to get the truncation behaviour. (Look at C compiler output.)

这篇关于除法和乘以2的幂的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！