求算法， 1,2,4,8,16…………，给出任意数如 15，如何计算出 15 是由 1， 2， 4， 8 相加得到的？即 15=1&2&4&8，而 13=1&4&8
bufannao · 2015-06-06 08:16:13 +08:00 · 3575 次点击这是一个创建于 3463 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
Xs0ul 2015-06-06 08:18:59 +08:00 via Android
看看十进制整数转换为二进制的算法
|
 |
2
wbingeek 2015-06-06 08:20:31 +08:00
除二取余
|
 |
3
hpeng 2015-06-06 08:26:47 +08:00 via Android
算二进制位数的1。位运算即可
|
 |
4
bufannao OP 能给个算法么？
function count($num){ // $num = 13 …… return $result; // array[1,4,8] } |
 |
5
zhjits 2015-06-06 08:29:09 +08:00 via Android
|
 |
8
ebony0319 2015-06-06 08:45:25 +08:00 via Android
说错了，但是二楼是正解
|
 |
9
wy315700 2015-06-06 08:46:20 +08:00  1
$i = 1;
$result = array(); while($num){ if($num & 1){ $result[] = $i; } $i *= 2; $num /= 2; } |
 |
10
zyue 2015-06-06 10:31:43 +08:00
不就是转为二进制么
|
 |
11
zhs227 2015-06-06 10:36:56 +08:00 1
php有现成的函数转二进制。话说直接求代码真是个不好的方式，至少这个问题很简单。
function count_a($num) { $result = []; foreach (array_reverse(str_split(decbin($num))) as $k=>$v ) { if ($v) { $result[] = 1<<$k; } } return $result; // array[1,4,8] } |
 |
12
SoloCompany 2015-06-06 11:35:45 +08:00 via iPad 1
toString(2)
|
 |
13
b821025551b 2015-06-06 11:45:11 +08:00
加号写成按位与也是醉了，我反应半天才反应过来
|
 |
14
imn1 2015-06-06 12:13:42 +08:00
换成二进制，看哪位有1就知道了
这是用整数作为权限表常见方法 |
|
15
bufannao OP |
 |
17
Jaylee 2015-06-06 13:47:37 +08:00
求子集
|
 |
18
xff1874 2015-06-06 16:38:21 +08:00
1 先排序
2 用贪婪算法 |
 |
19
327beckham 2015-06-07 01:03:13 +08:00
算法的话，加减乘除的速度有点慢了。用位运算的方式来弄吧。
|
 |
20
msg7086 2015-06-07 09:54:12 +08:00
发个ruby的好了
def bin n l = [] while n > 0 do m, n = n, n & (n-1); l << m - n end l end p bin 15 #-> [1, 2, 4, 8] |
|
21
msg7086 2015-06-07 10:00:25 +08:00
或者写成one line的话
bin = -> (n) {Enumerator.new{|e| while n > 0 do m, n = n, n & (n-1); e.yield m - n end}.to_a} p bin.call 15 #-> [1, 2, 4, 8] |
Select Language