Java

Integer.bitCount 的函式解析 要計算整數以二進制的方式表示時，所有 bit 位為 1 的總和。 雛形 從低位開始，檢查是否為 1。 public static int bitCount(int i){ int count = 0; while (i > 0) { if ((i & 1) == 1) // 如果最低位為 1，count就加 1 count++; i >>= 1; // 向右推進 1 位，等同於 num /= 2; } return count; } 時間複雜度為 \(O(n)\)，\(n\) 為整數的位數(bit 數)。 優化 利用(i - 1) & i 可以消除最低位數的 1 的性質來計算。 public static bitCount(int i){ int count = 0; while (i > 0){ i = i & (i - 1); // 0b0101_1100 - 1 = 0b0101_1011, 且 0b0101_1100 & 0b0101_1011 = 0b0101_1000; count++; } return count; } 時間複雜度為 \(O(n))\)，\(n\) 為位數為 1 的個數。 利用 int 的特性再優化 因為 int 的最大正整數為 2^31，故我們可以兩兩錯位相加來求和 private static int bitCount(int i){ i = (i & 0x55555555) + ((i >>> 1) & 0x55555555); // 0b0101_0101_0101_0101_0101_0101_0101_0101 i = (i & 0x33333333) + ((i >>> 2) & 0x33333333); // 0b0011_0011_0011_0011_0011_0011_0011_0011 i = (i & 0x0f0f0f0f) + ((i >>> 4) & 0x0f0f0f0f); // 0b0000_1111_0000_1111_0000_1111_0000_1111 i = (i & 0x00ff00ff) + ((i >>> 8) & 0x00ff00ff); // 0b0000_0000_1111_1111_0000_0000_1111_1111 i = (i & 0x0000ffff) + ((i >>>16) & 0x0000ffff); // 0b0000_0000_0000_0000_1111_1111_1111_1111 return i; } 時間複雜度為 \(O(1))\)。 Source Code(final) 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; } 一、三、四、五步不進行消位，在最後再利用 i & 0x3f 消去不必要的位數

HashMap.comparableClassFor(Object x) 的函式解讀 原文敘述 Returns x’s Class if it is of the form “class C implements Comparable”, else null. 我的翻譯 當x的類別為Comparable的實作時，返回x的類別；否則返回 null。 藉由這個函式實例的解讀，可以了解一下類別、泛型的相關概念。 Source Code static Class<?> comparableClassFor(Object x) { if (x instanceof Comparable) { Class<?> c; Type[] ts, as; ParameterizedType p; if ((c = x.getClass()) == String.class) // bypass checks return c; if ((ts = c.getGenericInterfaces()) != null) { for (Type t : ts) { if ((t instanceof ParameterizedType) && ((p = (ParameterizedType) t)....

List of Generics equality Case In leetcode no. 39 Combination Sum gives Given an array of distinct integers candidates and a target integer target, return a list of all unique combinations of candidates where the chosen numbers sum to target. You may return the combinations in any order. The same number may be chosen from candidates an unlimited number of times. Two combinations are unique if the frequency of at least one of the chosen numbers is different....