给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合

新浪微博 QQ空间 腾讯微博

给定一个long型常量,其值为x,给定long型变量a,要求a & x 的取值集合,结果放入ArrayList中。

思路,x先转换为bit数组,得出其中元素值为1的总数为n,则所有取值的总数为2的n次方,记为N。
在0~N的闭区间中,依次取出各个数值,记为tmp,将tmp也转换为bit数组,依次遍历x的每一个bit位,当x的bit位为1时,到tmp中去取出相应的bit位,如果也为1,则将该位为1时,其他所有位为0时所代表的数值累加到结果中。
遍历完所有的bit位后,得到的结果即为所需要的数值。

整个思路有点复杂,性能也不高,从数值本身的与或运算上面着手,肯定还有更简单的方法。

代码:

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 = 58;
if (x > maxvalue)
{
x = x & maxvalue;
}

Set<Long> aset = new TreeSet<Long>();

for (long i = 0; i <= x; i++)
{
aset.add(i & x);
}

System.out.println(aset);
aset = null;

List<Long> resList = new ArrayList<Long>();
byte[] bitArray = long2BinaryArray(x);
long max = 0;
int j = 0;
for (int i = 0; i != bitArray.length; i++)
{
if (bitArray[i] == '1')
{
max += Math.pow(2, j);
j++;
}
}

int maxlength = bitArray.length;
for (long i = 0; i <= max; i++)
{
long result = 0;
byte[] tmp = long2BinaryArray(i);
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);
}
}
}
}
resList.add(result);
}
System.out.println(resList + " : " + resList.size());
}

private static byte[] long2BinaryArray(long num)
{
String binaryString = Long.toBinaryString(num);
byte[] bitArray = binaryString.getBytes();
return bitArray;
}
}

 
 
运算结果:
[0, 2, 8, 10, 16, 18, 24, 26, 32, 34, 40, 42, 48, 50, 56, 58]
[0, 2, 8, 10, 16, 18, 24, 26, 32, 34, 40, 42, 48, 50, 56, 58]

新浪微博 QQ空间 腾讯微博

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

5 条评论

  1. liuqzh_hws
    评论于 七月 29, 2013 at 22:56:32 CST | 评论链接
    package test.bit.ops;
    
    import java.io.PrintStream;
    
    public class AnotherTestMain {
    
        public static void main(String[] args) {
            long x = 58;
            writeResult(x, System.out);
        }
    
        /*
         * 因为一个数组可能无法存放全部的结果,这里将结果输出
         */
        public static void writeResult(long num, PrintStream ps) {
    
            /*
             * java里没有无符号类型,这里不考虑负数
             */
            if (num < 0 || ps == null) {
                return;
            }
    
            /*
             * 0的话就不费劲了
             */
            if (num == 0) {
                ps.print(0);
            }
    
            /*
             * 计算传入的数字中,二进制表示串里有多少个1
             * 经典方法
             */
            int numOfSetBits = 0;
            long v = num;
            while (v > 0) {
                v &= (v - 1);
                numOfSetBits++;
            }
    
            /*
             * 将各个1表示对应的二进制的值存下来
             * 保存到一个数组中
             */
            long[] valueOfBits = new long[numOfSetBits];
            long pos = 1;
            int i = 0;
    
            while (i < numOfSetBits) {
                if ((pos & num) != 0) {
                    valueOfBits[i++] = pos;
                }
    
                pos <<= 1;
            }
    
            /*
             * 其实结果的个数与传入参数的二进制串中的1的个数有关系
             * 结果的个数 = Math.power(2, numOfSetBits)
             */
            long resultsNum = (1L << numOfSetBits);
            ps.print(0);
            for (long l = 1L; l < resultsNum; l++) {
                v = 0;
                for (i = 0; i < numOfSetBits && i < l; i++) {
                    if (((1L << i) & l) != 0) {
                        v |= valueOfBits[i];
                    }
                }
                ps.print(", ");
                ps.print(v);
            }
        }
    }
    

     

  2. nlqlove
    评论于 九月 8, 2012 at 23:29:58 CST | 评论链接
    // test.cpp : Defines the entry point for the console application.
    //
    
    #include "stdafx.h"
    #include 
    #include 
    
    #define LIST std::list
    #define STACK std::stack
    
    /************************************************************************/
    /*  求一个给定的x和任意一个数a的 x & a的值                              */
    /************************************************************************/
    bool GetSumOfAnd(long x, long a, size_t uPos, LIST& lstRst) 
    {
    	if (uPos >= sizeof(long)*8)
    	{
    		return false;
    	}
    
    	size_t uCurPos = uPos;
    
    	// 找到第一个非0 的bit位,自高位开始
    	do 
    	{
    		long i = 1;
    		i<<=uCurPos;
    
    		if (i & x) break;   // 该位为1则返回
    
    	}while(uCurPos--);
    
    
    	if (0xffffffff == uCurPos) // 如果是最后一位,且为0的情况
    	{
    		lstRst.push_back(a<<1);
    	}
    	else if (0 == uCurPos)     // 最后一位,且为1的情况
    	{
    		lstRst.push_back(a<<1 + 1);
    		lstRst.push_back(a<<1);
    	}
    	else
    	{
    		GetSumOfAnd(x, (a<<(uPos - uCurPos + 1)), uCurPos - 1, lstRst);
    		GetSumOfAnd(x, (a<<(uPos - uCurPos + 1)) + 1, uCurPos - 1, lstRst);
    	}
    
    	return true;
    }
    
    int main(int argc, char* argv[])
    {
    	LIST lstRst;
    	
    	GetSumOfAnd(580, 0, sizeof(long)*8 - 1, lstRst);
    	
    	LIST::iterator it = lstRst.begin();
    	for ( ;it != lstRst.end(); it++)
    	{
    		printf("%d\n", *it);
    	}
    
    	return 0;
    }

     

    • Yanqun
      评论于 九月 9, 2012 at 00:46:59 CST | 评论链接

      赞,这样简单高效,我写的那个太烂了!

    • Yanqun
      评论于 九月 9, 2012 at 10:40:28 CST | 评论链接

      F:\Source_Code\myprogs\myprog\axproblem\Release>axproblem.exe 1132442325
      consumed time: 187ms.

      C++只用了187毫秒。呆会测试一下Java递归算法的耗时。

      • nlqlove
        评论于 九月 9, 2012 at 11:58:02 CST | 评论链接

        递归主要函数调用开销比较大, 用stack来模拟实现回溯,效率应该可以再提一些。 而且还不会有栈溢出的风险。

评论

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

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>

返回顶部