Find rightmost set bit efficiently

[@jaatharsh]

Most efficient way O(1) for finding Right Most Bit No (i.e, integer whose binary representation has that bit 'ON' i.e, set to 1) Formula is a) num & ~(num-1) or can also be written as b) num & (num * -1) // lets understand with a) and example below num = 5 in binary (0000 0101) num-1 = 4 in binary (0000 0100) ~(num-1) = -5 in binary (1111 1011) // Negation results in all bits changing to opposite values 0 to 1 and 1 to 0 num & ~(num-1) = (0000 0101) & (1111 1011) = (0000 0001) = 1 in Decimal system

[@7akon]

Still in order to find the rightmost set bit from the result (eg: 0010000) , we have to iterate all the way to the left. So I believe in terms of efficiency, Brian Kernighan's method, upon which your solution is based is on par with Methods 1 and 3 of this video.

[@naive-fleek7420]

@@7akon just take log with base 2 and 1 . u will get the answer

[@akshatpandey007]

Log2(n^(n&(n-1))) can compute in O(log N) time

[@HarshGupta-if2xg]

love your explanation thank you so much

[@AniketSomwanshi-ll7mz]

How is the last method any better than the previous one?

[@kanchiseekers]

Time complexity is same in all the 3 cases right.

[@abhishek24leo]

Just do n & (-1 * n). Most efficient.

[@sourabhkumar6194]

hey bro , i know when we do this get rightmost set bit , but didn't able to understand what calculations are done in binary..if you can tell then please share it..

[@bishtman12]

Try for 6636. The answer should be 3. But it will return 4

[@agraa]

Good explanation. Just in doubt about time complexity. As we need to check bits for max 2 max 64 or 32 or 16 as per processor architecture. So i think it should be O(1)

[@bishtman12]

No, at every step we are basically dividing the number by 2. So, it's log2N.

[@jaatharsh]

thanks fr the video :)

[@dc6940]

Algorithm with mask is still O(n) where n is no of bits in the number. Lets suppose we have 1 in MSB, alg runs for every bit by right shift.

[@techdose4u]

Yea correct, it will be O(log N base 2). But since no of bits are generally fixed like 32 or 64 etc therefore, you can say O(1) for for fixed lower values.

[@shishpalvishnoi7974]

Your some playlist contain same video multiple time. e.g in Bit operation playlist Counting Bits is repeated 18 times. please fix it.

[@techdose4u]

😅 That's youtube error. Dunno why this is happening. But will fix it.

[@kirtigera2225]

Sir which software you r using for this?

[@techdose4u]

For teaching? It's Ink2Go

[@kirtigera2225]

@@techdose4u sir you r using it in Laptop?

[@kirtigera2225]

@@techdose4u sir means for writing in it we need a tab or we can use mouse for it?

[@techdose4u]

You will need a tablet

[@venkateshthirunagiri85]

Good 👨‍🏫👨‍🏫👨‍🏫👨‍🏫

[@techdose4u]

Thanks :)

[@SHIVAMTIWARI-we9jq]

I think in 3rd method we can also reduce number by n=n>>1

[@good-ty8zp]

it will also work n&(~n+1)

[@kanishkumar6176]

Rightmostbit = n &(-n)

[@RAHUDAS]

N^[N&(N-1)] this is the most efficient way not the one u share

[@iammituraj]

What do you even mean by "4 will be converted to binary and takes lot of time for large number"? Every number and computation is done at binary level at the lowest level by any computing device. There is no "decimal in computers", that's only for humans. Misleading video.