Java - Big O of bitCount()?

Question

What is the Big O of bit count? I'm not sure how the method works, but I would assume it is done in O(logn).

Specifically with this code (where x = 4, y = 1):

return Integer.bitCount(x^y);

What's `n` in your `O(log n)`? The total number of bits in the integer? When talking about Big O we set some arbitrary operation to have cost 1, and it's fair to assume `bitCount` has cost 1. — Mephy, May 29 '17 at 21:13
Actually I'd imagine it's `O(1)`, see e.g. https://stackoverflow.com/questions/1458314/number-of-1s-in-32-bit-number — jonrsharpe, May 29 '17 at 21:14

score 7 · Accepted Answer · edited May 29 '17 at 22:42

7

Given its implementation, the method consists of six O(1) statements performed in sequence, so it's O(1).

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;
}

edited May 29 '17 at 22:42

OneCricketeer

179,855
19
132
245

answered May 29 '17 at 21:14

RedXIII

781
7
6

2

The JVM is free to implement it differently than the code you see in the JDK source, and in fact it does since it is a "known function". Usually it compiles down to a single `popcnt` instruction on platforms that support it (most of the interesting ones). Doesn't really change the conclusion though (although it does mean that `Integer.bitCount()` and `Long.bitCount()` usually take the same time - which wouldn't be the your conclusion if you looked at the source. – BeeOnRope May 29 '17 at 21:18

score 2 · Answer 2 · answered May 29 '17 at 21:15

2

It is O(1), here is its implementation for JDK 1.5+:

public static int bitCount(int i) {
    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;
}

answered May 29 '17 at 21:15

syntagma

23,346
16
78
134

In practice, this implementation isn't used because on most platforms `Integer.bitCount` and several other simple methods in the `Integer`, `Long`, etc classes are implemented as JVM intrinsics which usually result in a single `popcnt` type instruction being emitted. Still O(1) though :) – BeeOnRope May 29 '17 at 21:16
That sounds reasonable but can you point to some source code that implements this using JVM intristics (I have found source code which uses exactly the code pasted)? – syntagma May 29 '17 at 21:18
1

Yes, you have do dig into the C++ source of the JVM. To see if a method is intrinsified check out the [vmSymbols.hpp](http://hg.openjdk.java.net/jdk8/jdk8/hotspot/file/87ee5ee27509/src/share/vm/classfile/vmSymbols.hpp) for your version of the JVM and look for the function name. In this case you find a line like `do_intrinsic(_bitCount_i, java_lang_Integer, bitCount_name, int_int_signature, F_S)` which indicates that the function is _potentially_ an intrinsic. – BeeOnRope May 29 '17 at 21:21
At this point you'd have to dig into the `.cpp` source to see if it actually _is_ on the platform of interest (usually it is once you find it in the `.hpp` but it may not be for several reasons such as the lack of support on a particular platform, etc). In the case of `bitCount` it usually ends up being an instrinsic on modern platforms of interest. Another approach is just to execute the method in question in a hot loop and then use something like `perf top` to check out the instruction(s) being executed. See also [this question](https://stackoverflow.com/q/19892322/149138). – BeeOnRope May 29 '17 at 21:23
Thanks, that's interesting. – syntagma May 29 '17 at 21:25
... and since I'm being exhaustive, another approach is to copy paste the JDK into a renamed function and then benchmark the original copy and exact copy. If it's normal, not intrinsic code you should get the same time. I tried it now and for `Integer.bitCount()` I get ~2.0 billion calls to `bitCount` per second, while for an exact copy of the JDK code I get only 0.4 billion calls/second. – BeeOnRope May 29 '17 at 21:38
@BeeOnRope I didn't know the JVM could supersede an existing source implementation. Is the concept covered in the JLS? Also, what exactly is the difference between intrinsic and native methods? – shmosel May 29 '17 at 21:40
1

@shmosel - as far as I know all intrinsic methods _also_ have a JDK implementation, so that's actually the general rule. The implementation needs to be there since (a) not all platforms may support the intrinsic version (b) there are times when the intrinsic is not used (e.g., in the interpreter) or when debugging and (c) in principle the JDK source is portable to JVM implementations that don't intrinsify stuff. You won't find any mention of this in the JLS - it's at a much lower level. Even the JVM spec won't mention it. It's like how C++ compilers recognize `memcpy` and replace it, often. – BeeOnRope May 29 '17 at 21:43
@shmosel - `native` methods are very different. This _is_ part of the JVM spec (probably the `native` keyword is briefly mentioned in the JLS as well) for implementing JNI methods. Basically you have a C-like function in some binary, and that function is called and does its work and returns. There are rules for how parameters are passed and various other things. It should work on any platform, etc - although of course you need to include different libraries for different architectures. – BeeOnRope May 29 '17 at 21:46
Intrinsic "methods" on the other hand are quite different in that they are replaced by the JIT in the compiled assembly code. There is no native code sitting around and no function is called. There are just some instructions inside the implemenation of the JIT compiler that says, "hey there is this `popcnt` assembly instruction, use it when you are compiling code that uses `Integer.bitCount`. There is effectively zero overhead, while `native` calls have an overhead of 20 cycles or more, usually. @shmosel – BeeOnRope May 29 '17 at 21:47
You can think of intrinsic methods as a way of extending java bytecode to cover more primitive operations without actually extending the bytecode (making it operational). There is no `popcnt` bytecode, but by telling the JIT about the special methods in the `Integer` class it's almost like there was. Some methods pretty much _have_ to be implemented as an intrinsic, like the methods in the `Atomic*` classes: those methods have the `native` keyword but they are actually instrinsics under the covers... – BeeOnRope May 29 '17 at 21:49

score 0 · Answer 3 · answered Jul 06 '21 at 16:06

0

Any algorithm that work on input of limited size have complexity of O(1).

bitCount works with input of limited size.

Therefore bitCount have complexity of O(1).

answered Jul 06 '21 at 16:06

talex

17,973
3
29
66

Java - Big O of bitCount()?

3 Answers3