java - Which code performs better in terms of Time-complexity? -

below 2 java codes find number of 1 bits in integer n.

code 1:

int count = 0;  while (n != 0) {     n = n & (n - 1);     count++; }  return count; 

code 2:

int = n; = - ((i >>> 1) & 0x55555555); = (i & 0x33333333) + ((i >>> 2) & 0x33333333); = (i + (i >>> 4)) & 0x0f0f0f0f; = + (i >>> 8); = + (i >>> 16); return & 0x3f; 

as far understand, first approach has complexity of o(n), while second 1 o(1). second 1 supposed better.

however not sure it.

you have take care when talking time complexity. big-o provides measure of asymptotic runtimes, means need measure runtimes arbitrarily large n. programming languages not provide (by default) int types arbitrarily large fudge issue bit , pretend do.

the first code snippet works if pretend int can large possible. runs 1 loop per 1 in binary representation of n, in worst case takes log_2(n) iterations. it's o(log n).

the second code snippet doesn't work (that is, produces wrong results) if int larger 32 bits. if imagine int getting larger support larger ns need in asymptotic analysis, we'd need more lines in program support bits needed represent n. because program has change correct, asymptotic analysis isn't possible. particular version of program runs in o(1) time, doesn't produce correct results large enough n, it's not fair comparison against first code snippet.

you can try fix second program adapt size of n instead of having hardcoded shifts , adds, using loop. think runs in o(log(log(n))) time since each additional shift doubles number of bits aggregated.

one important thing bear in mind we're assuming shifts , bitwise operations still o(1) no matter we're making int larger , larger. that's assumption quite common make in these analyses, it's not that's true on actual computers machine instructions work on 4 or 8 byte quantities only.

dynamic version of algorithm 2

your question java, here's correct o(log(log(n)) version of algorithm 2 in python (which have arbitrarily large ints). can treat pseudo-code if don't know python -- think relatively readable anyhow, , converting use java bignums make harder understand. computes k, number of bits needed represent n, rounded power of 2, , constructs list of shifts , masks necessary count bits. takes o(log(k)) time, , since k=log(n), overall algorithm takes o(log(log(n)) time (where here time means bitwise or arithmetic operations).

def generate_ops(k):     ops = []     mask = (1 << k) - 1     while k:         ops.append((k, mask))         k >>= 1         mask = mask ^ (mask << k)     return reversed(ops)  def bit_count(n):     k = 1     while (1 << k) < n:         k *= 2     shift, mask in generate_ops(k):         n = (n & mask) + ((n >> shift) & mask)     return n