Poison

发表于

Richard Startin 在文章 A Quick Look at RoaringBitmap 中介绍 BitmapContainer 提到 Long.bitCount 在处理器支持的情况下，会被内联为调用指令 popcnt 实现。本文做简单记录，我们编写如下的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
package me.tianshuang;

public class IntrinsicTest {

    public static void main(String[] args) {
        int result = 0;
        for (int i = 0; i < 1000000000; i++) {
            result += Long.bitCount(i);
        }

        System.out.println(result);
    }

}
阅读全文 »
Poison

发表于
获取二进制表示中最右侧为 1 的比特位

已知 -x = ~x + 1 ，我们可以使用 x & (-x) 得到二进制表示中最右侧的 1：

1
2
3
4
5
6
7
8
9
若 x 的二进制表示为：
11011100
则 ~x 的二进制表示为：
00100011
则 -x = ~x + 1 的二进制表示为：
00100100

则 x & (-x) 的二进制表示为：
00000100

其中 JDK 中的 Integer.lowestOneBit 就采用了以上的方法实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Returns an {@code int} value with at most a single one-bit, in the
 * position of the lowest-order ("rightmost") one-bit in the specified
 * {@code int} value.  Returns zero if the specified value has no
 * one-bits in its two's complement binary representation, that is, if it
 * is equal to zero.
 *
 * @param i the value whose lowest one bit is to be computed
 * @return an {@code int} value with a single one-bit, in the position
 *     of the lowest-order one-bit in the specified value, or zero if
 *     the specified value is itself equal to zero.
 * @since 1.5
 */
public static int lowestOneBit(int i) {
    // HD, Section 2-1
    return i & -i;
}
去除二进制表示中最右侧为 1 的比特位

因为 x - 1 会使最低位 1 右侧的 0 全部变为 1 且最低位 1 同时变为 0，所以我们使用 x & (x - 1) 可以去除最低位的 1：


References

面试题15. 二进制中 1 的个数（位运算，清晰图解）
2-1 Manipulating Rightmost Bits

Poison

发表于

最近看 Richard Startin 关于 RoaringBitmap 的文章 A Quick Look at RoaringBitmap 时，提到 BitmapContainer 底层由 long[] 组成，内部使用了 Long.bitCount 计算容器的基数，此时会被优化为使用 CPU 指令 popcnt 实现，关于内联可以参考 JVM Intrinsics，本文先分析 bitCount 函数的实现机制，由于 Integer.bitCount 与 Long.bitCount 实现机制相同，就用 Integer.bitCount 进行分析。

首先从 Integer 的官方文档 Integer (Java Platform SE 8 ) 中，我们可以看到以下描述：

Implementation note: The implementations of the “bit twiddling” methods (such as highestOneBit and numberOfTrailingZeros) are based on material from Henry S. Warren, Jr.’s Hacker’s Delight, (Addison Wesley, 2002).

描述说明了 Integer 内部 bit 的相关方法实现来自于书籍 《Hacker’s Delight》，感兴趣的可以看看这本书籍。

阅读全文 »
Poison

发表于 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
package me.tianshuang;

public class Foo {

    private Helper helper = null;

    public Helper getHelper() {
        if (helper == null) {
            synchronized (this) {
                if (helper == null) {
                    helper = new Helper();
                }
            }
        }
        return helper;
    }

}

以上的双重检查实现并不安全，原因为编译器可以重排序代码以使 Helper() 构造函数中的代码在写入 helper 变量后执行。如果发生了这样的情况，那么在构造线程写入 helper 变量之后，但在它实际完成对象构造之前，另一个线程可以在完成初始化之前出现并读取 helper，此时，该线程可能会看到对 helper 对象的非空引用，但会看到 helper 对象字段的默认值，而不是构造函数中设置的值。

阅读全文 »
Poison

发表于

最近看 Joshua Bloch 的访谈 More Effective Java With Google’s Joshua Bloch 时，其中提到单元测试不足以确保代码能够正常工作，举了二分搜索的例子，二分搜索的文章详见：Google AI Blog: Extra, Extra - Read All About It: Nearly All Binary Searches and Mergesorts are Broken，本文在此作简要记录。

在 JDK 1.3.1_28 中 java.util.Arrays#binarySearch(int[], int) 的实现如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Searches the specified array of ints for the specified value using the
 * binary search algorithm.  The array <strong>must</strong> be sorted (as
 * by the <tt>sort</tt> method, above) prior to making this call.  If it
 * is not sorted, the results are undefined.  If the array contains
 * multiple elements with the specified value, there is no guarantee which
 * one will be found.
 *
 * @param a   the array to be searched.
 * @param key the value to be searched for.
 * @return index of the search key, if it is contained in the list;
 * otherwise, <tt>(-(<i>insertion point</i>) - 1)</tt>.  The
 * <i>insertion point</i> is defined as the point at which the
 * key would be inserted into the list: the index of the first
 * element greater than the key, or <tt>list.size()</tt>, if all
 * elements in the list are less than the specified key.  Note
 * that this guarantees that the return value will be &gt;= 0 if
 * and only if the key is found.
 * @see #sort(int[])
 */
public static int binarySearch(int[] a, int key) {
    int low = 0;
    int high = a.length - 1;

    while (low <= high) {
        int mid = (low + high) / 2;
        int midVal = a[mid];

        if (midVal < key)
            low = mid + 1;
        else if (midVal > key)
            high = mid - 1;
        else
            return mid; // key found
    }
    return -(low + 1);  // key not found.
}
阅读全文 »