算法练习·求出二进制数中存在多少个1

算法练习·求出二进制数中存在多少个1

题目:输入一个十进制数字,计算出这个十进制数字的二进制数中存在多少二进制位"1"

举例:

十进制二进制"1"的数量
81001
54710001000114
115151011001111101110

白银解法:

你需要知道如下理论

公式结果
a & 00
a & 1a

思路:

每次将二进制数组右移动一格,逻辑与 (&1) 运算,如果最后最后一位进制为是1,则结果为1,否则为0

    private static int countOne(int number){
        int counter = 0;
        while (number > 0){
            if((number & 1) == 1){
		//如果逻辑与预算等于1 则说明当前二进制位是1,计数器加一
                counter ++;
            }
            number = (number >> 1);
        }
        return counter;
    }

砖石解法:

    public static void main(String[] args) {
        System.out.println(countOne(11515)); // 10
	System.out.println(countOne(8));     // 1
	System.out.println(countOne(547));   // 4			
    }

    private static int countOne(int a){
        //拦截器
        int filter_1  = 0x55555555;
        int filter_2  = 0x33333333;
        int filter_4  = 0x0f0f0f0f;
        int filter_8  = 0x00ff00ff;
        int filter_16 = 0x0000ffff;

        int b = (a & filter_1)  + ((a >> 1)  & filter_1);
        int c = (b & filter_2)  + ((b >> 2)  & filter_2);
        int d = (c & filter_4)  + ((c >> 4)  & filter_4);
        int e = (d & filter_8)  + ((d >> 8)  & filter_8);
        int f = (e & filter_16) + ((e >> 16) & filter_16);

        return f;
    }

对以上解法是不是有点懵逼??不要急,一步一步图解

  • 拦截器含义如下 (32位计算机)
拦截器二进制
0x5555555501 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01
0x333333330011 0011 0011 0011 0011 0011 0011 0011
0x0f0f0f0f0000 1111 0000 1111 0000 1111 0000 1111
0x00ff00ff00000000 11111111 00000000 11111111
0x0000ffff0000000000000000 1111111111111111

以上是根据拦截器(16进制)转变为二进制的结果表

  • (a & filter_1) + ((a >> 1) & filter_1) 图解如下

oneSplit

总结

后面的操作和第一步一致,都是将已有的二进制数组整天往右移动一格,然后再和拦截器逻辑与预算,然后相加。当移动到最后一格的时候,那便是二进制位1出现的次数

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×