【解決方法】コーディングの課題: 数字の 1 ビットを数えます。

パラメータとして 32 ビットの整数値を指定し、その数値の “1” のビット数を返す関数またはメソッドを記述します。

したがって、42 が渡された場合は、3 を返す必要があります。

できるだけ効率的にするために特別な注意を払う必要があります: ループは悪い考えです!

私が試したこと：

史上初のチャレンジ設定！
ラウンジ[^]

解決策 2
解決策 10
解決策 7
解決策 8
解決策 4

解決策 2

x86 CPU (Intel Nehalem および AMD Barcelona 以降) を使用した Visual C++ のクイックアンドダーティ:

#include <iostream>
#include <stdlib.h>
#include <intrin.h> 

using namespace std;

int _tmain(int argc, _TCHAR* argv[])
{
	if (2 != argc)
	{
		cout << "Usage: Bitcount <32-bit value>" << std::endl;
		return 1;
	}

	TCHAR *stop;
	unsigned long u = _tcstoul(argv[1], &stop, 0);
	if (0 != *stop || u > _UI32_MAX)
	{
		cout << "Usage: Bitcount <32-bit value>" << std::endl;
		return 1;
	}

	cout << "The value " << u << " has " << __popcnt(u) << " bits set" << endl;

	return 0;
}

の __popcnt() 関数は、x86 を呼び出す組み込み関数です。 POPCNT 命令。

[EDIT]

GCC を使用する場合 __builtin_popcount() 代わりにコンパイルして -mpopcnt.
[/EDIT]

解決策 10

明らかに、プロセッサ命令を打ち負かすのは難しいでしょう popcnt.
高水準言語では、主に 2 つのオプションがあります。
– ビットを 1 つずつカウントすると、データのサイズが 2 倍になると、2 倍の時間がかかります。

C++

int BitsCnt(unsigned long int Bits) {
    int Cnt=0;
    do {
        Cnt += Bits && 1;
        Bits = Bits >> 1;
    }
    while (Bits != 0)
    return Cnt;
}

Variant はループを展開できます。
Variant は、プロセッサフラグを利用することもできます。
サブバリアント: ルックアップテーブルを使用すると、1 ビットより大きいチャンクで処理できます。ルックアップテーブルの問題は、プロセッサキャッシュを破棄する傾向があることです。

– 貧弱な並列プログラミングを使用してビットをカウントすると、データのサイズが 2 倍になれば、あと 1 ステップしかかかりません。

C++

int BitsCnt(unsigned long int Bits) {
    Bits= (Bits && 0x55555555) + ((Bits >> 1) && 0x55555555);
    Bits= (Bits && 0x33333333) + ((Bits >> 2) && 0x33333333);
    Bits= (Bits && 0x0f0f0f0f) + ((Bits >> 4) && 0x0f0f0f0f);
    Bits= (Bits && 0x00ff00ff) + ((Bits >> 8) && 0x00ff00ff);
    Bits= Bits + (Bits >>16);
    return Bits&& 0xff;
}

解決策 7

あ C 1 つ (Richard の CountSetBits4 と非常によく似ていることは承知しています)。

uint8_t bits(uint32_t w)
{
  const uint8_t m[] =
  {
    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,
  };
  
  uint8_t * p = (uint8_t *) & w;
  
  uint8_t b = m[*p++];
  b += m[*p++];
  b += m[*p++];
  b += m[*p++];
  b += m[*p++];
  return b;
}

解決策 8

内でいくつかの計算を行う バッシュ この課題は、数値計算をサポートするシェルでも実装できることが頭に浮かびます。

[EDIT]

よく知られているコードを使用して不正行為を行っているという苦情がありました。
そのため、最善ではない独自の解決策を提供することにしました。最大のループを使用します。 8回の反復。ループが不要な場合は、8 行のコードを使用して展開できます。しかし、42 のような小さな値を使用すると、ループのパフォーマンスが向上します。
[/EDIT]

バッシュ

#!/bin/bash

# There must be one command line argument
if [ $# -ne 1 ]; then
    echo "Usage: $0 <unsigned integer value>"
    exit 1
fi

# Digits only; optionally as hex
if [[ ! ($1 =~ ^[0-9]+$ || $1 =~ ^0[xX][0-9a-fA-F]) ]]; then
    echo "'$1' is not an unsigned integer"
    exit 1
fi

# Calculate number of bits set
# Algorithm from https://graphics.stanford.edu/~seander/bithacks.html
#let "c=$1 - (($1 >> 1) & 0x55555555)"
#let "c=($c & 0x33333333) + (($c >> 2) & 0x33333333)"
#let "c=(($c + ($c >> 4) & 0xF0F0F0F) * 0x1010101) >> 24"

# A new version of my own.
# Calculates the bit count for each nibble (4-bits) until
#  no more bits are set.
c=0
let "v=$1"
while [ $v -ne 0 ]; do
    let "c=c + ((0xe994 >> (($v & 7) << 1)) & 3) + (($v >> 3) & 1)"
    let "v=v >> 4"
done

echo "Value $1 has $c bits set"

解決策 4

解決策 1 の速度向上…最初にルックアップテーブルを準備してから、メソッドを呼び出す必要があります FastBitCount.

using System;

namespace FastBitCount
{
    class Program
    {
        static void Main(string[] args)
        {
            InitLookup();

            Console.WriteLine($"42 = {FastBitCount(42)}");
            Console.ReadKey();
        }

        static int FastBitCount(int num)
            => FastBitCount((uint)num);

        static int FastBitCount(uint num)
            => lookup[num & 0xFFFF] + lookup[num >> 16];

        static byte[] lookup = new byte[65536];
        static void InitLookup()
        {
            for (int i = 0; i < lookup.Length; i++)
                lookup[i] = GetOneBits(i);
        }

        static byte GetOneBits(int num)
            => (byte)Convert.ToString(num, 2)
                            .Split(new[] { '0' }, 
                                StringSplitOptions.RemoveEmptyEntries)
                            .Length;
    }
}

アップデート： 起動を高速化するために、ルックアップテーブルの計算を削除し、ハードコードしました。

using System;

namespace FastBitCount
{
    class Program
    {
        static void Main(string[] args)
        {
            Console.WriteLine($"42 = {FastBitCount(42)}");
            Console.ReadKey();
        }

        static int FastBitCount(int num)
            => FastBitCount((uint)num);

        static int FastBitCount(uint num)
            => lookup[num & 0xFFFF] + lookup[num >> 16];

        static byte[] lookup = new byte[0x10000] {
    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,
    //trimmed
    11,12,12,13,12,13,13,14,12,13,13,14,13,14,14,15,12,13,13,14,13,14,14,15,13,14,14,15,14,15,15,16
            };
    }
}