what is the time complexity of setting a kth bit of a number or clearing kth bit of a number is it O(1) or O(logn) ?whatever it is please state the reason—what is the complexity of preforming the shifting and doing AND or OR operations?
Time complexity issue
It is O(1) as i we have 64 bits (for long long) and doing all of this operation would cost at max 64 operations hence O(1).
So bit manipulation is considered O(1)
this means that the complexity for all the questions claear kth bit set kth bit count the total number of sets bits is O(1) no matter how large n is?
what is the time complexity of question: count the total set bits in an integer n --O(logn) or O(1)? and what is the time complexity for clear kth bit question --O(logn) or O(1)?
could be done in o(1)
just make mask s,t, at kth bit is 0. rest are ones and ‘&’ it with the original number
count the total set bits in an integer n- has both approaches of logn as well as n
Refer
Yes it is O(1) for all practical purpose.
But while comparing two bit manipulation method we compare them by checking number of bits that are checked in the process. Hence we give them O(n), O(logn) complexity based on number of bits they are checking in calculating the answer