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

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);
        }
    }
}

consumed 5750ms.

consumed 5703ms.

consumed 344ms.

F:\Source_Code\myprogs\myprog\axproblem\Release>axproblem.exe 16715775
consumed time: 266ms.