《求a & x 的取值集合》解答改进版

新浪微博 QQ空间

按照上一篇中提到的思路,最后问题的焦点在于:怎样快速找到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下性能都是最高的。字符串转换和循环遍历是性能的最大杀手。

新浪微博 QQ空间

| 1 分2 分3 分4 分5 分 (4.40- 5票) Loading ... Loading ... | 这篇文章归档在:C/C++, Java, 算法数据结构, 职业发展. | 永久链接:链接 | 评论(4) |

4 条评论

  1. 匿名
    评论于 十一月 5, 2014 at 08:51:08 CST | 评论链接
    void solve(LL x)
    {
        for(int i = x; i > 0; i = (i - 1) & x)
            cout << i << endl;
        cout << 0 << endl;
    }
    int main()
    {
        solve(58);
        return 0;
    }

     

  2. 匿名
    评论于 十一月 5, 2014 at 08:50:09 CST | 评论链接

    其实吧….两行代码就好了…

  3. nlqlove
    评论于 九月 10, 2012 at 21:35:54 CST | 评论链接

    递归方案:在每次递归中都会求解同一个问题,当前bit为1的位到下一bit为1的距离,这里可以使用记忆法,每一个距离只用计算一次,后更新到一个索引表。后续就只要用就可以了。

评论

邮箱地址不会被泄露, 标记为 * 的项目必填。

8 - 2 = *



You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <img alt="" src="" class=""> <pre class=""> <q cite=""> <s> <strike> <strong>

返回顶部