日期:2014-05-18  浏览次数:20623 次

请求算法思路
有这样一个需求,不大好表达,例子如下:

两个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操作