鸟语天空

统计值为1的位元数

作者：追风剑情 发布于：2019-3-15 12:42 分类：Algorithms

示例

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace ConsoleApp1
{
    class Program
    {
        static void Main(string[] args)
        {
            int x = 999;
            Console.WriteLine("统计结果: {0}", StatBit1Count(x) );
            Console.Read();
        }

        public static int StatBit1Count(int x)
        {
            Console.WriteLine("统计值为1的位元数");
            Console.WriteLine("x={0}={1}", x, IntToBinary(x));
            Console.WriteLine("打印一些常量值");
            Console.WriteLine("0x55555555={0}", IntToBinary(0x55555555));
            Console.WriteLine("0x33333333={0}", IntToBinary(0x33333333));
            Console.WriteLine("0x0F0F0F0F={0}", IntToBinary(0x0F0F0F0F));
            Console.WriteLine("0x00FF00FF={0}", IntToBinary(0x00FF00FF));
            Console.WriteLine("0x0000FFFF={0}", IntToBinary(0x0000FFFF));
            Console.WriteLine();

            // 分治策略
            // 先统计相邻2位的1个数,再统计相邻4位的1个数
            // 再统计相邻8位的1个数,再统计相邻16位的1个数

            // 打印过程
            Console.WriteLine("步骤1:");            
            int i1 = (x & 0x55555555);
            int i2 = ((x >> 1) & 0x55555555);
            int i = i1 + i2;
            Console.WriteLine(" {0}={1} \n+{2}={3}", IntToBinary(i1), i1, IntToBinary(i2), i2);
            Console.WriteLine(" -----------------------------------");
            Console.WriteLine(" {0}={1}", IntToBinary(i), i);
            // --end

            x = (x & 0x55555555) + ((x >> 1) & 0x55555555);

            // 打印过程
            Console.WriteLine("步骤2:");            
            i1 = (x & 0x33333333);
            i2 = ((x >> 2) & 0x33333333);
            i = i1 + i2;
            Console.WriteLine(" {0}={1} \n+{2}={3}", IntToBinary(i1), i1, IntToBinary(i2), i2);
            Console.WriteLine(" -----------------------------------");
            Console.WriteLine(" {0}={1}", IntToBinary(i), i);
            // --end

            x = (x & 0x33333333) + ((x >> 2) & 0x33333333);

            // 打印过程
            Console.WriteLine("步骤3:");
            i1 = (x & 0x0F0F0F0F);
            i2 = ((x >> 4) & 0x0F0F0F0F);
            i = i1 + i2;
            Console.WriteLine(" {0}={1} \n+{2}={3}", IntToBinary(i1), i1, IntToBinary(i2), i2);
            Console.WriteLine(" -----------------------------------");
            Console.WriteLine(" {0}={1}", IntToBinary(i), i);
            // --end

            x = (x & 0x0F0F0F0F) + ((x >> 4) & 0x0F0F0F0F);

            // 打印过程
            Console.WriteLine("步骤4");            
            i1 = (x & 0x00FF00FF);
            i2 = ((x >> 8) & 0x00FF00FF);
            i = i1 + i2;
            Console.WriteLine(" {0}={1} \n+{2}={3}", IntToBinary(i1), i1, IntToBinary(i2), i2);
            Console.WriteLine(" -----------------------------------");
            Console.WriteLine(" {0}={1}", IntToBinary(i), i);
            // --end

            x = (x & 0x00FF00FF) + ((x >> 8) & 0x00FF00FF);

            // 打印过程
            Console.WriteLine("步骤5:");
            i1 = (x & 0x0000FFFF);
            i2 = ((x >> 16) & 0x0000FFFF);
            i = i1 + i2;
            Console.WriteLine(" {0}={1} \n+{2}={3}", IntToBinary(i1), i1, IntToBinary(i2), i2);
            Console.WriteLine(" -----------------------------------");
            Console.WriteLine(" {0}={1}", IntToBinary(i), i);
            // --end

            x = (x & 0x0000FFFF) + ((x >> 16) & 0x0000FFFF);

            return x;
        }

        public static string IntToBinary(int val, int bits = 32)
        {
            string final = "";

            for (int i = bits; i > 0;)
            {
                if (i == 8 || i == 16 || i == 24) final += " ";
                final += ((val & (1 << --i)) != 0) ? '1' : '0';
            }
            return final;
        }
    }
}

运行测试

标签: Algorithms