请求算法思路
有这样一个需求,不大好表达,例子如下:
两个int类型的数a,b。 其中 a = 195,二进制表示为: 0000 0000 1100 0011
a = 0000 0000 1100 0011
第1次,让 b= 0000 0000 1000 0000
第2次, 让 b = 0000 0000 1100 0000
第3次, 让 b = 0000 0000 1100 0010
第3次, 让 b = 0000 0000 1100 0011
规律是:b 每次都是更新到a下一个为1的比特位置。
------解决方案--------------------从左往右扫描就可以了,要以用字符数组的方式来做,这个最简单。
也中以用一个32位的int来做,相对复杂一点
------解决方案--------------------我的思路(可能讲得不是很明白):
把a先化成十进制
然后
第一次b:2^x < a这个表达式求x的最大值,这个2^x值化成二进制就是第一次的b
然后把a = a - 2^x
第二次b:2^y < a这个表达式求y的最大值,这个2^y值化成二进制,再加上第一次的b就是第二次的b
然后把a = a - 2^y
第三次b:2^z < a这个表达式求z的最大值,这个2^z值化成二进制,再加上第二次的b就是第三次的b
……
以此类推
------解决方案--------------------利用十进制转二进制记录下1的位置,再利用二进制转十进制恢复
int a = 195;
int i = 0;
List<Integer> index = new ArrayList<Integer>();// 用于记录1出现的位置
while (a != 0) {
if (a % 2 != 0) {
index.add(0, i);
}
i++;
a /= 2;
}
int b = 0;
for (Integer j : index) {
b += power(j);
System.out.println(Integer.toBinaryString(b));
}
/**
* 计算2的N次幂
*
* @param i
* @return
*/
public static int power(int i) {
int k = 1;
for (int j = 0; j < i; j++) {
k *= 2;
}
return k;
}
------解决方案--------------------用一个数组记录a中1的位置,然后遍历,1<<位置之后得到的值与a位and操作