求二進制數中 1 的個數

原文位址:求二進制數中 1 的個數

歡迎通路我的部落格:http://blog.duhbb.com/

引言

有很多中方法可以計算一個整數二進制形式中的 1 的個數, 本文記錄兩種, 速度都還不錯. 第一個算法好記一點, 了解起來也簡單, 應該是首選了.

位移法

int BitCount(unsigned int n)
{
    unsigned int c = 0;
    for (c = 0; n; ++c)
    {
        // 清除最低位的 1
        n &= (n - 1);
    }
    return c;
}
           

JDK 中 Integer 的方法

/**
     * Returns the number of one-bits in the two's complement binary
     * representation of the specified {@code int} value.  This function is
     * sometimes referred to as the <i>population count</i>.
     *
     * @param i the value whose bits are to be counted
     * @return the number of one-bits in the two's complement binary
     *     representation of the specified {@code int} value.
     * @since 1.5
     */
    public static int bitCount(int i) {
        // HD, Figure 5-2
        i = i - ((i >>> 1) & 0x55555555);
        i = (i & 0x33333333) + ((i >>> 2) & 0x33333333);
        i = (i + (i >>> 4)) & 0x0f0f0f0f;
        i = i + (i >>> 8);
        i = i + (i >>> 16);
        return i & 0x3f;
    }
           

在 C++ 中把

>>>

換成

>>

.

結束語