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

作者：童燕群 | 发布日期：九月 8, 2012 | 阅读次数（11,734） | 评论（5） |

新浪微博 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 | 评论链接
    view source
    01package test.bit.ops;
    02 
    03import java.io.PrintStream;
    04 
    05public class AnotherTestMain {
    06 
    07    public static void main(String[] args) {
    08        long x = 58;
    09        writeResult(x, System.out);
    10    }
    11 
    12    /*
    13     * 因为一个数组可能无法存放全部的结果，这里将结果输出
    14     */
    15    public static void writeResult(long num, PrintStream ps) {
    16 
    17        /*
    18         * java里没有无符号类型，这里不考虑负数
    19         */
    20        if (num < 0 || ps == null) {
    21            return;
    22        }
    23 
    24        /*
    25         * 0的话就不费劲了
    26         */
    27        if (num == 0) {
    28            ps.print(0);
    29        }
    30 
    31        /*
    32         * 计算传入的数字中，二进制表示串里有多少个1
    33         * 经典方法
    34         */
    35        int numOfSetBits = 0;
    36        long v = num;
    37        while (v > 0) {
    38            v &= (v - 1);
    39            numOfSetBits++;
    40        }
    41 
    42        /*
    43         * 将各个1表示对应的二进制的值存下来
    44         * 保存到一个数组中
    45         */
    46        long[] valueOfBits = new long[numOfSetBits];
    47        long pos = 1;
    48        int i = 0;
    49 
    50        while (i < numOfSetBits) {
    51            if ((pos & num) != 0) {
    52                valueOfBits[i++] = pos;
    53            }
    54 
    55            pos <<= 1;
    56        }
    57 
    58        /*
    59         * 其实结果的个数与传入参数的二进制串中的1的个数有关系
    60         * 结果的个数 = Math.power(2, numOfSetBits)
    61         */
    62        long resultsNum = (1L << numOfSetBits);
    63        ps.print(0);
    64        for (long l = 1L; l < resultsNum; l++) {
    65            v = 0;
    66            for (i = 0; i < numOfSetBits && i < l; i++) {
    67                if (((1L << i) & l) != 0) {
    68                    v |= valueOfBits[i];
    69                }
    70            }
    71            ps.print(", ");
    72            ps.print(v);
    73        }
    74    }
    75}

     

    回复
  2. nlqlove
    评论于 九月 8, 2012 at 23:29:58 CST | 评论链接
    view source
    01// test.cpp : Defines the entry point for the console application.
    02//
    03 
    04#include "stdafx.h"
    05#include
    06#include
    07 
    08#define LIST std::list
    09#define STACK std::stack
    10 
    11/************************************************************************/
    12/*  求一个给定的x和任意一个数a的 x & a的值                              */
    13/************************************************************************/
    14bool GetSumOfAnd(long x, long a, size_t uPos, LIST& lstRst)
    15{
    16    if (uPos >= sizeof(long)*8)
    17    {
    18        return false;
    19    }
    20 
    21    size_t uCurPos = uPos;
    22 
    23    // 找到第一个非0 的bit位，自高位开始
    24    do
    25    {
    26        long i = 1;
    27        i<<=uCurPos;
    28 
    29        if (i & x) break;   // 该位为1则返回
    30 
    31    }while(uCurPos--);
    32 
    33 
    34    if (0xffffffff == uCurPos) // 如果是最后一位，且为0的情况
    35    {
    36        lstRst.push_back(a<<1);
    37    }
    38    else if (0 == uCurPos)     // 最后一位，且为1的情况
    39    {
    40        lstRst.push_back(a<<1 + 1);
    41        lstRst.push_back(a<<1);
    42    }
    43    else
    44    {
    45        GetSumOfAnd(x, (a<<(uPos - uCurPos + 1)), uCurPos - 1, lstRst);
    46        GetSumOfAnd(x, (a<<(uPos - uCurPos + 1)) + 1, uCurPos - 1, lstRst);
    47    }
    48 
    49    return true;
    50}
    51 
    52int main(int argc, char* argv[])
    53{
    54    LIST lstRst;
    55     
    56    GetSumOfAnd(580, 0, sizeof(long)*8 - 1, lstRst);
    57     
    58    LIST::iterator it = lstRst.begin();
    59    for ( ;it != lstRst.end(); it++)
    60    {
    61        printf("%d\n", *it);
    62    }
    63 
    64    return 0;
    65}

     

    回复
    • 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>