一个整数的有多少位的1?

Question

月末了，来个短平快的游戏，散分兼庆祝五一。要求，用C#来找出一个64位整数的机器码有多少位的1。比如CountBit（7） = 3 因为7写成二进制是111
比如CountBit（10） = 2 因为10写成二进制是1010一半分数将给算得最快的。环境： .Net2.0 C#编译器，采用Release， 开启优化， 允许非安全代码：
命令行编译为： csc.exe /optimize+ /checked- /unsafe /plateform:any CountBit.cs一天后将移到非技术区。以下是测试框架：
// CountBit.cs
using System;class Program
{
    static void Main()
    {
        Random random = new Random(123456);
        ulong[] testNumbers = new ulong[1000];
        for (int i = 0; i < testNumbers.Length; i++)
        {
            testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
        }        for (int tests = 0; tests < 10; tests++)
        {
            System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
            int sum = 0;
            sw.Start();
            for (int i = 0; i < loops; i++)
            {
                sum += CountBit(testNumbers[i % 1000]);
            }
            sw.Stop();
            Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
        }
    }    static int CountBit(ulong x)
    {
        //...
    }    static readonly int loops = 1000 * 1000;
}

Answer 1

using System;
using System.Text.RegularExpressions;
public class Test
{
    static void Main()
    {        string strGetRandom = GetRandom(64);
        int i = Method1(strGetRandom);
        int i2 = Method2(strGetRandom);
        int i3 = Method3(strGetRandom);
    }    static string GetRandom(int amount)
    {
        Random ran = new Random();
        string strResults = "";
        for (int i = 1; i <= amount; i++)
        {
            strResults += ran.Next(0, 9);
        }
        return strResults;
    }    static int Method1(string strGetRandom)
    {
        int beforeCount = strGetRandom.Length;
        strGetRandom = strGetRandom.Replace("1", "");
        int afterCount = strGetRandom.Length;
        return beforeCount - afterCount;
    }    static int Method2(string strGetRandom)
    {
        return Regex.Replace(strGetRandom, "[^1]", "").Length;
    }    static int Method3(string strGetRandom)
    {
        return Regex.Matches(strGetRandom, "1").Count;
    }
}呵呵!!!我也不知道哪个快!

Answer 2

先抛一个，效率不高，先蹭点分。
static int CountBit(ulong x)
{
    int result = 0;
    for (int i = 0; i < 64; i++)
        result += (int)((x >> i) & 1);
    return result;
}

Answer 3

using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class9
    {
        static void Main()
        {
            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                int sum = 0;
                sw.Start();
                for (int i = 0; i < loops; i++)
                {
                    sum += CountBit(testNumbers[i % 1000]);
                }
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
        }        static int CountBit(ulong x)
        {
            int r = 0;
            for (int i = 0; i < 64; i++)
            {
                if ((x >> i & 1) == 1) r++;
            }
            return r;
        }        static readonly int loops = 1000 * 1000;
    }
}

Answer 4

using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class9
    {
        static void Main()
        {
            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                int sum = 0;
                sw.Start();
                for (int i = 0; i < loops; i++)
                {
                    sum += CountBit(testNumbers[i % 1000]);
                }
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
        }        static int CountBit(ulong x)
        {
            int r = 0;
            for (int i = 0; i < 64; i++)
            {
                if ((x >> i & 1) == 1) r++;
            }
            return r;
        }        static readonly int loops = 1000 * 1000;
    }
}

Answer 5

呵呵，我先随便贴一个。      
  static int CountBit(ulong x)
        {
            int sum = 0;            while (x != 0)
            {
                if ((x & 1) != 0)
                    sum++;
                x /=2;            }
            return sum;
        }

Answer 6

查表的方式：
static int[] byteCounts = { 
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };static int CountBit(ulong x)
{
    return byteCounts[x & 0xFF] + byteCounts[x >> 8 & 0xFF] + 
        byteCounts[x >> 16 & 0xFF] + byteCounts[x >> 24 & 0xFF] +
        byteCounts[x >> 32 & 0xFF] + byteCounts[x >> 40 & 0xFF] +
        byteCounts[x >> 48 & 0xFF] + byteCounts[x >> 56 & 0xFF];
}

Answer 7

using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class9
    {
        static void Main()
        {
            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                int sum = 0;
                sw.Start();
                for (int i = 0; i < loops; i++)
                {
                    sum += CountBit(testNumbers[i % 1000]);
                }
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
        }        //static int CountBit(ulong x)
        //{
        //    int r = 0;
        //    for (int i = 0; i < 64; i++)
        //    {
        //        if ((x >> i & 1) == 1) r++;
        //    }
        //    return r;
        //}        static int CountBit(ulong x)
        {
            int r = 0;            if ((x >> 0 & 1) == 1) r++;
            if ((x >> 1 & 1) == 1) r++;
            if ((x >> 2 & 1) == 1) r++;
            if ((x >> 3 & 1) == 1) r++;
            if ((x >> 4 & 1) == 1) r++;
            if ((x >> 5 & 1) == 1) r++;
            if ((x >> 6 & 1) == 1) r++;
            if ((x >> 7 & 1) == 1) r++;
            if ((x >> 8 & 1) == 1) r++;
            if ((x >> 9 & 1) == 1) r++;
            if ((x >> 10 & 1) == 1) r++;
            if ((x >> 11 & 1) == 1) r++;
            if ((x >> 12 & 1) == 1) r++;
            if ((x >> 13 & 1) == 1) r++;
            if ((x >> 14 & 1) == 1) r++;
            if ((x >> 15 & 1) == 1) r++;
            if ((x >> 16 & 1) == 1) r++;
            if ((x >> 17 & 1) == 1) r++;
            if ((x >> 18 & 1) == 1) r++;
            if ((x >> 19 & 1) == 1) r++;
            if ((x >> 20 & 1) == 1) r++;
            if ((x >> 21 & 1) == 1) r++;
            if ((x >> 22 & 1) == 1) r++;
            if ((x >> 23 & 1) == 1) r++;
            if ((x >> 24 & 1) == 1) r++;
            if ((x >> 25 & 1) == 1) r++;
            if ((x >> 26 & 1) == 1) r++;
            if ((x >> 27 & 1) == 1) r++;
            if ((x >> 28 & 1) == 1) r++;
            if ((x >> 29 & 1) == 1) r++;
            if ((x >> 30 & 1) == 1) r++;
            if ((x >> 31 & 1) == 1) r++;
            if ((x >> 32 & 1) == 1) r++;
            if ((x >> 33 & 1) == 1) r++;
            if ((x >> 34 & 1) == 1) r++;
            if ((x >> 35 & 1) == 1) r++;
            if ((x >> 36 & 1) == 1) r++;
            if ((x >> 37 & 1) == 1) r++;
            if ((x >> 38 & 1) == 1) r++;
            if ((x >> 39 & 1) == 1) r++;
            if ((x >> 40 & 1) == 1) r++;
            if ((x >> 41 & 1) == 1) r++;
            if ((x >> 42 & 1) == 1) r++;
            if ((x >> 43 & 1) == 1) r++;
            if ((x >> 44 & 1) == 1) r++;
            if ((x >> 45 & 1) == 1) r++;
            if ((x >> 46 & 1) == 1) r++;
            if ((x >> 47 & 1) == 1) r++;
            if ((x >> 48 & 1) == 1) r++;
            if ((x >> 49 & 1) == 1) r++;
            if ((x >> 50 & 1) == 1) r++;
            if ((x >> 51 & 1) == 1) r++;
            if ((x >> 52 & 1) == 1) r++;
            if ((x >> 53 & 1) == 1) r++;
            if ((x >> 54 & 1) == 1) r++;
            if ((x >> 55 & 1) == 1) r++;
            if ((x >> 56 & 1) == 1) r++;
            if ((x >> 57 & 1) == 1) r++;
            if ((x >> 58 & 1) == 1) r++;
            if ((x >> 59 & 1) == 1) r++;
            if ((x >> 60 & 1) == 1) r++;
            if ((x >> 61 & 1) == 1) r++;
            if ((x >> 62 & 1) == 1) r++;
            if ((x >> 63 & 1) == 1) r++;            return r;
        }        static readonly int loops = 1000 * 1000;
    }
}

Answer 8

为啥我不能用右移操作符>>啊,一用他就报错说：“Only assignment,call,increment,decremnet and new Object expressions can be used as a statement”

Answer 9

不移位
using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class9
    {
        static void Main()
        {
            ulong hx;
            for (int i = 0; i < 64; i++)
            {
                hx = (ulong)Math.Pow(2, i);
                Console.WriteLine("if((x & {0}) == {0}) r++;", hx);
            }            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                int sum = 0;
                sw.Start();
                for (int i = 0; i < loops; i++)
                {
                    sum += CountBit(testNumbers[i % 1000]);
                }
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
        }        //static int CountBit(ulong x)
        //{
        //    int r = 0;
        //    for (int i = 0; i < 64; i++)
        //    {
        //        if ((x >> i & 1) == 1) r++;
        //    }
        //    return r;
        //}        static int CountBit(ulong x)
        {
            int r = 0;            if ((x & 1) == 1) r++;
            if ((x & 2) == 2) r++;
            if ((x & 4) == 4) r++;
            if ((x & 8) == 8) r++;
            if ((x & 16) == 16) r++;
            if ((x & 32) == 32) r++;
            if ((x & 64) == 64) r++;
            if ((x & 128) == 128) r++;
            if ((x & 256) == 256) r++;
            if ((x & 512) == 512) r++;
            if ((x & 1024) == 1024) r++;
            if ((x & 2048) == 2048) r++;
            if ((x & 4096) == 4096) r++;
            if ((x & 8192) == 8192) r++;
            if ((x & 16384) == 16384) r++;
            if ((x & 32768) == 32768) r++;
            if ((x & 65536) == 65536) r++;
            if ((x & 131072) == 131072) r++;
            if ((x & 262144) == 262144) r++;
            if ((x & 524288) == 524288) r++;
            if ((x & 1048576) == 1048576) r++;
            if ((x & 2097152) == 2097152) r++;
            if ((x & 4194304) == 4194304) r++;
            if ((x & 8388608) == 8388608) r++;
            if ((x & 16777216) == 16777216) r++;
            if ((x & 33554432) == 33554432) r++;
            if ((x & 67108864) == 67108864) r++;
            if ((x & 134217728) == 134217728) r++;
            if ((x & 268435456) == 268435456) r++;
            if ((x & 536870912) == 536870912) r++;
            if ((x & 1073741824) == 1073741824) r++;
            if ((x & 2147483648) == 2147483648) r++;
            if ((x & 4294967296) == 4294967296) r++;
            if ((x & 8589934592) == 8589934592) r++;
            if ((x & 17179869184) == 17179869184) r++;
            if ((x & 34359738368) == 34359738368) r++;
            if ((x & 68719476736) == 68719476736) r++;
            if ((x & 137438953472) == 137438953472) r++;
            if ((x & 274877906944) == 274877906944) r++;
            if ((x & 549755813888) == 549755813888) r++;
            if ((x & 1099511627776) == 1099511627776) r++;
            if ((x & 2199023255552) == 2199023255552) r++;
            if ((x & 4398046511104) == 4398046511104) r++;
            if ((x & 8796093022208) == 8796093022208) r++;
            if ((x & 17592186044416) == 17592186044416) r++;
            if ((x & 35184372088832) == 35184372088832) r++;
            if ((x & 70368744177664) == 70368744177664) r++;
            if ((x & 140737488355328) == 140737488355328) r++;
            if ((x & 281474976710656) == 281474976710656) r++;
            if ((x & 562949953421312) == 562949953421312) r++;
            if ((x & 1125899906842624) == 1125899906842624) r++;
            if ((x & 2251799813685248) == 2251799813685248) r++;
            if ((x & 4503599627370496) == 4503599627370496) r++;
            if ((x & 9007199254740992) == 9007199254740992) r++;
            if ((x & 18014398509481984) == 18014398509481984) r++;
            if ((x & 36028797018963968) == 36028797018963968) r++;
            if ((x & 72057594037927936) == 72057594037927936) r++;
            if ((x & 144115188075855872) == 144115188075855872) r++;
            if ((x & 288230376151711744) == 288230376151711744) r++;
            if ((x & 576460752303423488) == 576460752303423488) r++;
            if ((x & 1152921504606846976) == 1152921504606846976) r++;
            if ((x & 2305843009213693952) == 2305843009213693952) r++;
            if ((x & 4611686018427387904) == 4611686018427387904) r++;
            if ((x & 9223372036854775808) == 9223372036854775808) r++;            return r;
        }        static readonly int loops = 1000 * 1000;
    }
}

Answer 10

int countbit(uLong x)
int temp = 0;
int count = 0;
for(int i = 0;i< 64;i++)
{
   temp = x&0x01;
   if(temp == 1) count ++;
   x = x >> 1;
   temp = 0;
}

Answer 11

伴水查表的方法最快。vmm莫狡辩。

Answer 12

64bit的问题空间太大，不容易。

Answer 13

哈哈..改了一下 zswang 的代码，用指针快了几ms
using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class10
    {
        static void Main()
        {
            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                int sum = 0;
                sw.Start();
                for (int i = 0; i < loops; i++)
                {
                    sum += CountBit(testNumbers[i % 1000]);
                }
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
        }        static int[] byteCounts = { 
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };        static int CountBit(ulong x)
        {
            unsafe
            {
                byte** p = (byte**)&x;
                byte* p0 = (byte*)&p[0];
                byte* p1 = (byte*)&p[1];
                return byteCounts[p0[0]] + byteCounts[p0[1]] + byteCounts[p0[2]] + byteCounts[p0[3]] +
                    byteCounts[p1[0]] + byteCounts[p1[1]] + byteCounts[p1[2]] + byteCounts[p1[3]];
            }
        }
        static readonly int loops = 1000 * 1000;
    }
}

Answer 14

思路基本上是通过2进制位移的方法最快左移32次，每次左移后&1判断是否>1(实际上就是判断末尾是否0)，是则计数器++
int CountBit(int x) 
{ 
    int result = 0; 
    for (int i = 0; i  < 32; i++) 
        if ( ((x << i) & 1) > 1 ) result++ ; 
    return result; 
} 

Answer 15

using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class10
    {
        static int[] byteCounts = { 
            0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 
            4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8 };
        static int[] byteCounts16 = new int[65536];
        static void Main()
        {
            for (int i = 0; i < 65536; i++)
            {
                byteCounts16[i] = byteCounts[i & 0xFF] + byteCounts[i >> 8 & 0xFF];
            }
            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                int sum = 0;
                sw.Start();
                for (int i = 0; i < loops; i++)
                {
                    sum += CountBit(testNumbers[i % 1000]);
                }
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
            Console.ReadLine();
        }
        static int CountBit(ulong x)
        {
            return byteCounts16[x & 0xFFFF] + byteCounts16[x >> 16 & 0xFFFF] +
                byteCounts16[x >> 32 & 0xFFFF] + byteCounts16[x >> 48 & 0xFFFF];
        }
        static readonly int loops = 1000 * 1000;
    }
}

Answer 16

        static int CountBit(ulong x)
        {
            int sum = 0;            while (x != 0)
            {
                if ((x & 1) != 0)
                    sum++;
                x =x>>1;            }
            return sum;
        }

Answer 17

16位查表是快很多。
finished in   54ms, checksum = 30894000
finished in   54ms, checksum = 30894000
finished in   55ms, checksum = 30894000
finished in   52ms, checksum = 30894000
finished in   57ms, checksum = 30894000
finished in   52ms, checksum = 30894000
finished in   51ms, checksum = 30894000
finished in   51ms, checksum = 30894000
finished in   51ms, checksum = 30894000
finished in   55ms, checksum = 30894000

Answer 18

如果要缓存计算结果,我觉得这样最快:
using System;
using System.Collections.Generic;
using System.Text;namespace TempTestA1
{
    class Class11
    {
        static void Main()
        {
            Random random = new Random(123456);
            ulong[] testNumbers = new ulong[1000];
            for (int i = 0; i < testNumbers.Length; i++)
            {
                testNumbers[i] = ((ulong)random.Next() << 33) + (ulong)random.Next();
            }
            // 缓存结果
            int sum = 0;
            for (int i = 0; i < loops; i++)
            {
                sum += CountBit(testNumbers[i % 1000]);
            }
            for (int tests = 0; tests < 10; tests++)
            {
                System.Diagnostics.Stopwatch sw = new System.Diagnostics.Stopwatch();
                sw.Start();
                sw.Stop();
                Console.WriteLine("finished in {0,4}ms, checksum = {1}", sw.ElapsedMilliseconds, sum);
            }
        }
        static int CountBit(ulong x)
        {
            int r = 0;
            for (int i = 0; i < 64; i++)
            {
                if ((x >> i & 1) == 1) r++;
            }
            return r;
        }
        static readonly int loops = 1000 * 1000;
    }
}结果:
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000
finished in    0ms, checksum = 30894000

Answer 19

很强大，不知道你要这个Stopwatch起啥作用？

Answer 20

中间都没有语句，当然是0ms了。
sw.Start();
sw.Stop();
不如直接地，更简单：
Console.WriteLine("finished in 0ms, checksum = 30894000");

Answer 21

【灌水脚本】在回复中，DIY一个选择表情的对话框！

Answer 22

看来楼上的都没我快,哈哈!!!!!Console.WriteLine("finished in -100000000000ms");

Answer 23

据说start（）和 stop（）之间是有时间的。

Answer 24

我想这个不一定最快，但是从速度和代码简洁结合上看是最好的：    int CountBit(ulong x)
    {
        int c = 0;
        while(x > 0)
        {
            if ((x & 1) != 0) c++;
            x >>= 1;
        }
        return c;
    }

Answer 25

我的测试结果[code=BatchFile]
L11_zswang        292ms
L12_r_swordsman   626ms
L14_yatobiaf     2342ms
L15_zswang         40ms
L16_r_swordsman   470ms
L25_r_swordsman   353ms
L31_ls443085074   355ms
L34_r_swordsman    21ms     //<---
L39_viena          20ms     //<---
L41_yatobiaf      425ms
L64_edyang        425ms
LZ__test           41ms
[/code]测试方法：
[code=BatchFile]
@ECHO OFF
:START
IF "%1"=="" GOTO :ENDECHO
ECHO %1
csc.exe /optimize+ /checked- /unsafe /define:%1 CountBit.cs >nul
CountBit.exeSHIFT
GOTO :START
:END[/code]测试的结果没有办法准确，这里有跳表的解析度原因，有测试本身循环的开销影响等等，差别10ms左右就当误差吧。我只将贴出代码的放入测试，只写方法或推荐他人而没有写代码的朋友就这次对不住了。目前的结果是34楼r_swordsman和39楼viena跑得最快，但15楼zswang最先提出查表的思路。
给分从来都不会完全公正的。viena58楼的帖子解决了我的难题。我想：
zswang     100
r_swordsman 40
viena       40
写代码的朋友  5谢谢大家，分数不多抱歉抱歉。

Answer 26

L34 _r_swordsman只是把伴水的代码改为了unsafe的，没啥创意
不如我的16位查表有创意，但是我的16位表也是用伴水的8位表生成的
我的16位查表如果也改为unsafe的，速度应该比现在提高不少
但r_swordsman在本帖的参与度最高，没有功劳也有苦劳
总之同意楼主的给分方案~

Answer 27

这里是我知道的算法之一，它用了分半逐个解决的方法。
 1 1 1 0 0 0 0 1           // 两个两个相加
|   |   |   |   |
 1 0 0 1 0 0 0 1           // 四个四个相加
|       |       |
 0 0 1 1 0 0 0 1           // 八个八个相加
|               |
 0 0 0 0 0 1 0 0           // 答案    static int CountBit(ulong x)
    {
        x = (x & 0x5555555555555555L) + ((x >> 1) & 0x5555555555555555L);
        x = (x & 0x3333333333333333L) + ((x >> 2) & 0x3333333333333333L);
        x = (x & 0x0F0F0F0F0F0F0F0FL) + ((x >> 4) & 0x0F0F0F0F0F0F0F0FL);
        x = (x & 0x00FF00FF00FF00FFL) + ((x >> 8) & 0x00FF00FF00FF00FFL);
        x = (x & 0x0000FFFF0000FFFFL) + ((x >>16) & 0x0000FFFF0000FFFFL);
        x = (x & 0x00000000FFFFFFFFL) + ((x >>32));
        return (int)x;
   }
一般来说条件执行会降低执行效率，这次表现好的基本都没有循环的开销和条件执行的开销。
游戏一下大家轻松快乐，也很高兴看到了又长又粗的用法。把循环解开有时候是可以增加效率。不过建议初学的朋友们万万不可像我这里这样写代码。我记得有两句话：
最好的优化就是不要去优化。
最好的优化就是以后再去优化。

Answer 28

楼主的问题可以变化一下更有意思！求从1到N中总共有多少位1？N为1-4294967295中任意一个数值(即：uint类型)