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...