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

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来模拟实现回溯，效率应该可以再提一些。 而且还不会有栈溢出的风险。

       回复