微信扫描,分享到朋友圈和群
《求a & x 的取值集合》解答改进版
按照上一篇中提到的思路,最后问题的焦点在于:怎样快速找到tmp中的为1的bit位在x中的实际位置。这样在计算N值的同时将每一位的权值与索引位置的关系用数组对照起来,最后只需要在遍历tmp的值为1的bit位时作相应的加权累加即可。
也综合评论中提到的递归方案,重新补充了各个方案的代码和性能测试代码。
见“方案1”的代码处:
package test.bit.ops;
import java.util.ArrayList;
import java.util.List;
import java.util.Set;
import java.util.TreeSet;
public class TestMain
{
public static void main(String[] args)
{
final long maxvalue = Long.MAX_VALUE;
long x = 0xFF0FFFl;
if (x > maxvalue)
{
x = x & maxvalue;
}
// rightResult(x);
long startTime, endTime;
startTime = System.currentTimeMillis();
List<Long> resList = new ArrayList<Long>();
// getSumOfAnd(x, 0, 63, resList); // 递归方案
bitOpMethod(x, resList);
endTime = System.currentTimeMillis();
// System.out.println(resList + " : " + resList.size());
System.out.println("consumed " + (endTime - startTime) + "ms.");
}
private static void bitOpMethod(long x, List<Long> resList)
{
byte[] bitArray = long2BinaryArray(x);
int maxlength = bitArray.length;
int[] indexArray = new int[64];
long max = 0;
int j = 0;
for (int i = maxlength - 1; i >= 0; i--)
{
if (bitArray[i] == '1')
{
max += Math.pow(2, j);
indexArray[j] = maxlength - 1 - i;
j++;
}
}
for (long i = 0; i <= max; i++)
{
byte[] tmp = long2BinaryArray(i);
// 方案1
// resList.add(calResult2(indexArray, tmp));
// 方案2
resList.add(calResult(bitArray, maxlength, tmp));
}
}
private static void rightResult(long x)
{
Set<Long> aset = new TreeSet<Long>();
for (long i = 0; i <= x; i++)
{
aset.add(i & x);
}
System.out.println(aset + " : " + aset.size());
}
private static long calResult2(int[] indexArray, byte[] tmp)
{
long result = 0;
int ltmp = tmp.length;
for (int s = ltmp - 1; s >= 0; s--)
{
if (tmp[s] == '1')
{
result += Math.pow(2, indexArray[ltmp - 1 - s]);
}
}
return result;
}
private static long calResult(byte[] bitArray, int maxlength, byte[] tmp)
{
long result = 0;
int ltmp = tmp.length;
for (int s = maxlength - 1; s >= 0; s--)
{
if (bitArray[s] == '1')
{
if (ltmp <= 0)
{
break;
}
else
{
ltmp--;
if (tmp[ltmp] == '1')
{
result += Math.pow(2, maxlength - 1 - s);
}
}
}
}
return result;
}
private static byte[] long2BinaryArray(long num)
{
String binaryString = Long.toBinaryString(num);
byte[] bitArray = binaryString.getBytes();
return bitArray;
}
private static void getSumOfAnd(long x, long a, int uPos, List<Long> lstRst)
{
if (uPos >= 64)
{
return;
}
int uCurPos = uPos;
// 找到第一个非0 的bit位,自高位开始
do
{
long i = 1;
i <<= uCurPos;
if ((i & x) != 0)
{
break; // 该位为1则返回
}
} while (uCurPos-- != 0);
if (0xFFFFFFFF == uCurPos) // 如果是最后一位,且为0的情况
{
lstRst.add((a << 1));
}
else if (0 == uCurPos) // 最后一位,且为1的情况
{
lstRst.add((a << 1) + 1);
lstRst.add((a << 1));
}
else
{
getSumOfAnd(x, (a << (uPos - uCurPos + 1)), uCurPos - 1, lstRst);
getSumOfAnd(x, (a << (uPos - uCurPos + 1)) + 1, uCurPos - 1, lstRst);
}
}
}
计算结果:
方案1:
consumed 5750ms.
方案2:
consumed 5703ms.
递归方案,在Java环境下:
consumed 344ms.
C++代码:
F:\Source_Code\myprogs\myprog\axproblem\Release>axproblem.exe 16715775
consumed time: 266ms.
方案1和2的对比可以看出,并没有优化,两者的性能相当。从递归位移运算的方案来看,位移运算无论是在C++代码中还是在JVM下性能都是最高的。字符串转换和循环遍历是性能的最大杀手。
4 条评论
赞,写了一堆代码,见笑了 ^_^
其实吧….两行代码就好了…
递归方案:在每次递归中都会求解同一个问题,当前bit为1的位到下一bit为1的距离,这里可以使用记忆法,每一个距离只用计算一次,后更新到一个索引表。后续就只要用就可以了。