编程中用移位运算替代乘除法会不会有问题？

[jssyxzy]

因为移位运算实际上有算术移位，逻辑移位，循环移位；
又有有符号数，无符号数；
不同编程语言有可能实现不同。

请问这里面有没有什么坑？

[reus]

不懂就不要用

[cheesea]

会挨揍，除非确实有必要。

[shore507]

没必要最好不用，强行装逼会挨揍的

[luozic]

业务代码最好不要使用， 框架单元测试写得多，可以在框架里面用，优化性能。

[8023]

在性能相对较差的单片机上，这样写二进制下的整乘整除，可以加快运行速度。但在电脑上这么写就没任何用处了。

[pathletboy]

大部分现代编译器会尽可能把 2 的 n 次方的乘除法优化为左移右移。

[hjlmjx]

移植性差是一方面吧？

[x86vk]

cpp 的话，没必要这么做，一般编译器都会做优化，具体可以参考一下 microcai 的某篇博文。

用左移右移代替乘除法的话一般是不会出问题的，只有在遇到浮点型的数据的时候才会出现问题。

[yanaraika]

在 编译器质量差的编译器上才这么做，如果你的编译器是近 5 年内发布的，那么没有这么做的必要

[jssyxzy]

我觉得楼上诸位太那个了，我问的不是工程问题，是科学问题好么？
我只想搞清楚这个。

[rabbbit]

会
例如 Javascript,位运算只支持 32 位
超出边界时会有意向不到的效果

Python
3 << 30
# 3221225472L

JavaScript
3 << 30
// -1073741824

除了 leetcode 想不到还有哪里需要位运算了

[ermao]

@rabbbit 哈哈哈面向 Leetcode 编程

[mengzhuo]

hacker's delight 了解一下

[stevenbipt]

感觉 11 楼说得没毛病😄😄😄😄😄

[pynix]

强行装逼最致命。。。

[redsonic]

我只想说 linux 内核里面各种位移，随便用乘除要被喷死。至于动态语言里面就变装逼，可能就是解释器的问题了，或是平台转换时候的各种坑。

[smdbh]

你每次乘除都是 2 幂么？

[meteor957]

内马尔为什么总被踢……

[jssyxzy]

我真是不懂怎么这么多人纠结这个？
位移本来就比乘除法快，虽然这个东西对于大多数硬件来说微不足道；
但是不要学没有见过世面好么？
这个确实很多方面要用到，比如编译器优化，汇编代码，单片机等。

[jssyxzy]

好吧，这个问题应该是我找错地方问了，应该多在 V2EX 多问问工程类问题。

[jssyxzy]

@rabbbit 嗯，位运算定义里面有如果移位数超过大小，结果是未定义的。

[li1215101]

写一句在后面要写一堆注释，过几天有人改了一下代码，忘记补注释就 gg

[zjyl1994]

你直接写乘除，剩下的让编译器来优化。现在不是 1980 年的电脑也不是那个年代的编译器了。

[cs923]

看 Java 的一些集合类源码也用到了位运算 应该能提升效率 也只是了解😄

[shijingshijing]

我比写编译器的人聪明系列。。。

[msg7086]

楼上几位说得也没错啊。
乘除法编译优化完本来就会变成其他玩意儿。
你写 a = a * 5，编译完就成 a = (a << 2) + a 了。
有符号无符号这些都是编译器帮你处理的。

又比如[1]
a = a / 19
编译完会变成
t = a * 2938661835 >> 32;
a = (t + ((a - t) >> 1) >> 4) & 0x0fffffff;

你问会不会有问题？会有问题啊。问题在你没编译器那么聪明严谨……

[1]: How do compilers optimize divisions? https://zneak.github.io/fcd/2017/02/19/divisions.html

[zzj0311]

csapp lab1，先去玩玩再说科学

[tempdban]

有用，有的情况必须写
上面的答案假设的情况不约而同都是用变量和常量做运算，折中情况编译器都能很好的优化。
都没考虑 第一个操作数 是变量 第二个操作数是个只要程序运行就能确定下来的变量
也就是说第二个变量初始化后就不会变。
最近性能优化大量的用了相关技巧 提升了 5%左右的性能 再加上其他优化手法，提升了 35%。

[tempdban]

楼上还有嘲讽“我比写编译器的人聪明系列”，大可不必这样。像我们这种一个任务需要执行几个指令周期都要细扣的领域，编译器的优化甚至有可能产生副作用。
很多代码写出来的效果很难看但是性能会爆炸的高。
你说的写法在特定的场合一定都是有用的，这里面会有坑尤其是，不同平台现象上会有差别，要多查多试。
知道什么时候该用而不是一棒子打死，你会领先很多人一个身位。

[ericls]

Linter 都过不了

[chinvo]

这是传说中的“只有我这种用汇编的人才见过世面”系列么？

不要为了追求“优化”滥用位移，降低代码可读性。

gcc 和 clang 现在已经默认启用 2 的幂乘除法到位移的优化，而在 py js java c# 之类的语言上同类优化机制也是存在的。不知道这些机制还非要强行开喷，怕不是不仅没见过世面连计算机科学基础都没学好。

或者大兄弟你还在用“先进的” VC++ 6.0 ？

至于在不存在自动优化或者刻意忽略 /禁用自动优化的情况下，写成位移对效率提升确实是有用的，但是必须自己处理溢出等问题。

明明就是个工程型（应用）的问题，非要扯什么“科学”（数理），还把楼上的诸位喷一个“没见过世面”，简直了。

[gnaggnoyil]

@jssyxzy 单片机?据我所知就算是 diab compiler,默认也会进行整数乘除至移位的优化,更不用说现在那么多单片机工具链不过就是 clang 换了层皮.而且既然你说到单片机,那看样子是在写 C/C++?C/C++里的整数的移位要么是确定的语义要么就是未定义行为,只要照着标准文档来就不会出现未预期的结果,除非 diab 或者 clang 有 bug.哪里有坑了?

[yangqi]

用之前先搞清楚为什么要用。

[imn1]

我写脚本用位运算不少，但不是为了优化
我更多是为了计算「位」
例如： $num >> 7 & 1
我目的是要知道$num 第八位是 1 还是 0，实际意义就是第八个权限：[ 有 | 无 ]

[zwh2698]

一般情况的场景，模拟器，虚拟机，部分算法，web 好像没有这个必要，因为上层已经将底层给包装了很多次，简单的区分一下，如果不是 c 或者 c plus 就基本用不着

[bk201]

看你什么工程了,视情况分析做程序员这个不懂说不过去.

[proudzhu]

负数处理结果不一致

[hatsuyuki]

移位比乘除效率高

[nihiue]

提前优化不可取，应该先完成功能，然后找出性能热点，针对性优化

[shijingshijing]

@tempdban 不知道你在那个平台上写的。

1，现代编译器普遍对乘法除法进行了优化，右移这种操作输入入门级的了。除非你手动强制关闭优化再换手写位移，这种情况有没有？我只见过很 PIC 单片机上做电机控制有这种操作。

2，现代 cpu 很多都集成了 FMA （也有叫 fmadd ）的指令，包括 nvidia 的 gpu，一条 FMA 指令一次能完成一个加乘操作，使用 fma 指令只需要你把两个乘数放进去，然后把被加数置为 0，一个 cycle 后取结果即可。还需要你多花几个周期移来移去？

[shijingshijing]

@shijingshijing 爪机打字错误百出，修订：
输入入门级 -> 属于入门级
见过很 PIC -> 见过在 PIC

补充，1，PIC 这种单片机用位移做乘法也是有编译器或者库可以用的，真没必要手写。
2，FMA 指令不仅能做乘法，其实除法也是用 FMA 来做的，A/B 实际上是把被除数 B 先取倒数，然后再与 A 乘。

多了解一下现代处理器的 ISA 吧

[miaomiaoweiwei]

强行装逼不可取 哈哈

[billwsy]

@shijingshijing fma 一个周期取结果真的么…

[billwsy]

@tempdban 固定值的变量的话会被 CSE common subedpression elimination 优化掉…

除非是从 caller 传进来或者是全局变量…那真的不怕万一被改了？怕被改了就加个 if 判断，然后 CSE 继续给优化了…

当然得承认有些技巧还是有用的…

[shijingshijing]

@billwsy 嗯，这个是我的疏忽，我的意思你懂的，一条指令搞定的基本上都是硬件级的，远比自己软件折腾来的快得多和靠谱的多。

用位移替代乘除，我能想到的就两种情形：
1，片上资源紧张，又需要用到乘除而且没精度要求；

2，大数的乘除。

[shijingshijing]

@imn1 你这个其实一条按位与操作就行了：

$num & 10000000b

返回结果 true or false

[xuboying]

楼主非要强行装就很无聊了，你说是科学问题，那么就把位移和乘法除法等效的过程证明一遍就好了，然后你用不同的语言实现你的证明过程就行了，然后就可以结贴了。
自己有又想编译器优化，那么就看汇编怎么实现乘法除法就好了

[jssyxzy]

题目描述有歧义，把标题 "编程中" 换成 “理论上”。

[Cu635]

@redsonic
不懂不要乱说。
“至于动态语言里面就变装逼”谁都没说，说的理由其实就是 C 语言编译器的优化，至少 gcc 是会做优化的，乘除法能优化的就优化到位运算。

@jssyxzy
你再看看自己发的帖子是啥，是怎么描述的。
就是因为“这个确实很多方面要用到，比如编译器优化”，既然编译器已经帮助你优化了，自然的你在编程过程中就不需要费事了。
单片机、嵌入式这种当然还是需要的。

@tempdban
“都没考虑 第一个操作数 是变量 第二个操作数是个只要程序运行就能确定下来的变量
也就是说第二个变量初始化后就不会变。 ”
这种情况下，编译器同样能够优化，只不过可能不是默认行为，而是要由你来配置编译参数，或者不是编译器所有版本都支持，需要你有意识的来选择一个版本比较新的。

“像我们这种一个任务需要执行几个指令周期都要细扣的领域，编译器的优化甚至有可能产生副作用。 ”
这是搞单片机还是嵌入式的？

@chinvo
“或者大兄弟你还在用“先进的” VC++ 6.0 ？”
呃，现在 VS 花里胡哨的太多了，VC++6.0 毕竟功能简单一些，作为入门比较合适……

@imn1
“例如： $num >> 7 & 1
我目的是要知道$num 第八位是 1 还是 0，实际意义就是第八个权限：[ 有 | 无 ]”
这个时候难道不是用掩码？

@shijingshijing
问题就是，tempdban 老兄的开发环境不一定是新版本编译器啊，那种单片机嵌入式的开发环境很多版本都是非常非常老的……

[mooncakejs]

@rabbbit 据我所知，c 系语音，32 位整数都是这个结果。

[CoderGeek]

用来做标志位的时候会用到 比如一些开关
0 1 2 4 8 16 32 64 代表每个打开状态

[CoderGeek]

int[] code = { 0, 1 << 0, 1 << 1, 1 << 2, 1 << 3, 1 << 4 }
后期做&判断啥的 = =

[imn1]

@shijingshijing
@Cu635
我知道，但这样直观
序号 19 就 >> 19-1，不用去算掩码

[firebroo]

我觉得看啥场景吧。。
当然现在的编译器真心优化的挺牛逼的。。之前看过一点 https://www.firebroo.com/categorys/3cb6da3228424ff7c02df7ad7f8cfd3acc9265ee12f515ee875f075f03edbfbc/articles/7bd1dee60330ecaddf114cfb93528054a65ed1e4c8250ce37bf9d1d05a1f92ad
就好比大家都觉得写汇编会比写 c 效率高，但是如果不是精通汇编，我觉得优化不过编译器。。

[tempdban]

@Cu635 这个值不是每次上电初始化都不一样，但是一旦初始化了在整个运行时都不变。这样编译器也会优化么？
我只是对最大可能的值做了一个单独的分支 进来这个分支就死循环住，因为能进这个分支就说明这个值是确定的，这个值一确定,就有很多东西能优化成常量位移操作，进而编译器优化掉。
是做数据面转发的

[yanaraika]

除非你知道编译器不知道的信息 /能做编译器不能做的语义修改 /特殊的向量指令，否则能打得过 clang 6.0 -O3 -flto + PGO + ipa-pta 算我输

[tempdban]

@shijingshijing

@billwsy
首先还是给点了个感谢

比如 a % b
这个 b 是在程序初始化中经过统计得来的，但是一旦 b == 8 呢
我做的只是
If b == 8
while (1) a & 7
else
while (1) a % b

这种操作一个两个还好，可是如果有大量的呢
我是反汇编加 vtune 性能采集对过的，这么写对我来讲效果很好，而且实际情况选比我们在这讨论来的复杂 比如说我们只能开 O2 O3 上来就会段错误。
我们的编译器确实已经很老了，连内核都是 2.6.x 的。
这东西谁敢说换，一旦换了是不是要投入很多人？

我们调了半年的代码，就为了让流水线打满，可别让我再了解 ISA 了，了解不动了兄弟。

[billwsy]

@tempdban 感谢！这倒是一个很不错的例子，看看做编译器的人能不能挖一挖，说不定是篇很好的 paper 呢

[Raymon111111]

带来不了足够的性能优势

写这种代码, 可读性第一

如果你认为能显著带来性能上优化, 给出报告再说吧

[yanaraika]

@tempdban O3 段错误的代码是怎么敢上线的……

[tempdban]

@yanaraika 用 O2 编就好了啊，为何不敢，在线上的还没出过事故呢。

[zhidian]

可以用位移，但不能是为了加速乘法。你要弄一个 mask 啥的，当然可以用位移。

[tlday]

@jssyxzy 我也没搞清楚你在纠结啥，你问的明明就是一个工程问题，却非要说是科学问题。大家热心回答你的问题，答案你不满意，你就甩来一句“没见过世面”，大家伙欠你的啰？

[lance6716]

这么牛逼怎么不知道看看语言 ref

[jssyxzy]

@tlday 那我来告诉你纠结什么，我只想知道这个究竟是否完全等价，转换有什么可能出现错误的地方，所以我说这是科学问题；但是一堆人回答我，我当然知道他们说的是什么意思，说的是可读性和可维护性么，所以他们说的是工程问题。
如果不能理解，我换个说法，我问二叉树实现的某个细节问题，一堆人回我，这个用不到，高级语言都封装了，直接调 api 就行了，然后告诉我怎么用 api，你觉得我什么感受。
当然我的题目歧义很大，我指的是我自己的私人的编程，可能大多数工作的都会理解自己工作的编程。

[jssyxzy]

@tlday https://henrikwarne.com/2012/12/12/working-as-a-software-developer/

[tempdban]

@jssyxzy 我也有点这个感受

[mingl0280]

@jssyxzy 有可能，自己写会有各种意想不到的细节问题……比方说位丢失啊什么的乱七八糟的问题……

[fcten]

在原生支持整数操作的语言中，一般来说在没有溢出的情况下都是等价的。但是在很多“高级”语言中，位运算往往是模拟的，这种时候是否等价就和该语言的具体实现相关了。

比如说 JavaScript，因为 JavaScript 中 number 是只有浮点型的，所以 JavaScript 的位运算只能在浮点数上操作。由于浮点数操作上的一些坑，你会得到以下结果：

(0.7+0.1)*10 << 1 = 14
(0.7+0.1)*10 * 2 = 15.999999999999998

[jzq526]

可以，但没有必要，一则是代码可读性降低，二则要兼顾不同的平台（如果考虑移植的话），三则可以通过位移实现的乘除法，编译器可以自己优化，去年看的一本书上说的

[wsy2220]

谁在我这里用,我打死他

[x86vk]

@smdbh 做快速幂也是可以的。

[mandy0119]

大概科学都不考虑代码可读性的问题吧。我们这边位运算只有表示状态更改状态时候用

[yanaraika]

@tempdban O3 也是完全符合标准的。O3 会 segfault 说明代码中有未定义行为，O2 正常运行也许只是“表现得”正常，实际哪里多写了一个字节、在某些特定输入下就会炸这种定时炸弹是比起崩溃更加不稳定的因素。我们团队这边都采用 O3 编译，一旦出现问题必须及时定位，尽早发现问题而不是掩盖问题

[tempdban]

@yanaraika O3 符合标准，是谁的标准？
你怎么就能确定我们的代码经过 O3 优化后，编译出来的东西，就一定是我们想表达的意思？

[tempdban]

@yanaraika 我还是那句话，有的事情远比你我在这里讨论的情况，还要复杂

[miketeam]

我有个业务还是必须用移位操作。就是一秒发送 5000 个数据包，然后里面不断除法计算…

[yanaraika]

@tempdban 当然是 ISO/IEC 9899 与 ISO/IEC 14882。 如果不是你们表达出的意思，那么要么是编译器的 bug （小概率），大概率你们写的根本就不是 well-defined C/C++，这和编译不过属于同等严重的问题。当然，你们可以认为自己是 Linus，giving gcc a f*ck，但 Linux kernel 在 O3 下可是没有任何问题的；或者直接因为招不到靠谱 /足够的人接着在冰上走，这就和“编程”没有任何关系了。

[tempdban]

@yanaraika 其实我并不觉得写未定义行为的代码，就是问题，更谈不上是严重的问题。
我们这套代码用了十多年了，好多东西都是静态库直接分发的，能 O3 的部分早就 O3 了。
历史包袱有多重，你想不到的兄弟，就这样上边还嫌需求开发的慢呢，本来 O2 能跑，就为了一点虚无缥缈的性能，你非要换成 O3，线上炸了，这个责任谁接，炸了的这部分代码和你一点关系都没有？ O2 加上特殊的代码写法，能达到我们要的性能，何必换呢？
再说 O3 又不是一定会带来性能提升，我贴一段话：

-O3 has several disadvantages:

First of all it often produces slower code than -O2 or -Os. Sometimes it produces longer code due to loop unrolling which may be in fact slower due to worse cache performance of code.
As it was said it sometimes produces wrong code. It may be either due to error in optimalization or error in code (like ignoring strict aliasing). As kernel code sometimes is and sometimes have to be 'smart' I'd say it is possible that some kernel developer made some error. I experienced various strange problems, like crashing of userspace utilities, when I compiled kernel with gcc 4.5 which at that point was stable. I still use gcc 4.4 for kernel and several selected userspace utilities due to various bugs. The same may apply for -O3.
I don't think it offers much benefit for the Linux kernel. The kernel does not do heavy computations and in places it does, it is optimized with assembly. -O3 flag will not change the cost of context switching or speed of I/O. I don't think something like <0.1% speedup of overall performance is worth it.

只要是能稳定，性能不差，O2 又能怎样。
招不到靠谱的人，兄弟，不是说这十几年里每个人都是会写 well-defined 的代码，要是人人都这样，那还要做什么测试，直接发布就得了。
理想很丰满啊哥们。

[ligo]

只有乘除 2^n 这个特例才可以，然而编译器会自动优化。