一道初级的算法题

V2EX = way to explore

V2EX 是一个关于分享和探索的地方

现在注册

已注册用户请登录

推荐关注

› Meteor

› JSLint - a JavaScript code quality tool

› jsFiddle

› D3.js

› WebStorm

推荐书目

› JavaScript 权威指南第 5 版

› Closure: The Definitive Guide

这是一个创建于 2528 天前的主题，其中的信息可能已经有所发展或是发生改变。

做一道 codewars 上面初级的一道算法题看到的别人的答案。（ js 写的）

二进制转十进制，我能看得懂没问题。

就是不知道其中的数学原理是什么？

还是我想多了，没有那么多道理，纯属智商问题？......

const binaryArrayToNumber = arr => {
  return arr.reduce((a,b)=>(a<<1|b),0);
};

算法

十进制

初级

arr

9 条回复 • 2017-12-16 15:15:46 +08:00

bilibalao

2017-12-16 02:31:19 +08:00 via iPhone

https://stackoverflow.com/questions/42089749/calculating-binary-of-array-using-array-reduce
不是智商的问题，是遇到问题不知道自己去主动解决问题的 case

siteshen

2017-12-16 03:00:41 +08:00

这段代码确实是用了些数学知识，再用了一点点 trick，因而比较难以理解。
我这给不了严格的数学证明，只能帮助你直观理解下。

S0 = a
S1 = ax + b = S0*x + b
S2 = ax^2 + bx + c = (ax + b)x + c = S1*x + c
S3 = ax^3 + bx^2 + cx + d = S2*x + d
...
Sn = S{n_1}*x + 常数项

特定到这道题，x = 2，a, b, c, .. 为 0 或者 1 （输入为二进制数组）
a * x + b = a * 2 + b = (a<<1) + b = a << 1 + b
最后一步用的小 trick：因为 a << 1 mod 2 = 0，b 为 0 或 1，所以 a<<1 | b = a * 2 + b

msg7086

2017-12-16 03:15:18 +08:00

什么数学原理？这不就是手动计算二进制数的算法吗？
每读一位就把前面的乘 2 然后加上后面的数字。

binux

2017-12-16 05:43:59 +08:00 via Android

对位操作和 reduce 不敏感

bjrjk

2017-12-16 08:15:38 +08:00 via Android

这个是高中数学课本内容，秦九昭算法。。。

we2ex

2017-12-16 12:17:07 +08:00 via Android

看不懂就自己写一个，对比一下就懂了

jaychenjun

2017-12-16 14:24:03 +08:00 via Android

@we2ex 我可以看懂，就是不知道为什么可以这样做

msg7086

2017-12-16 14:36:35 +08:00

@jaychenjun 大概是 a * 2 + b 变成 a<<1 | b 这部分没看懂？

jaychenjun

2017-12-16 15:15:46 +08:00

@siteshen

我懂了，谢谢，我就是不知道前面乘二加再后面的原理是什么，

我之前更熟悉的方法都是从右往左开始算(第一位的二次幂置为 0，然后依次加一，没有涉及到位运算，就是要多声明几个变量...)

然后我把你式子换成下面这种，发现从左往右的道理和从右往左一样，只是数学式子换了一个形式而已。

S3 = ax^3 + bx^2 + cx^1 + dx^0
= ( ( a * x + b ) * x + c ) * x + d ...