Competitive Programming with Python-Bit Magic- Power of 2 + One's in Binary Representation of Number

Bit Magic
Description: We will code for following topics
1.Power of 2
2.One's in Binary Representation of Number

#CompetitiveProgramming #ProgrammingKnowledge #BitMagic #NumberTheory #Python #Sieve #BitMagic
★★★Top Online Courses From ProgrammingKnowledge ★★★

★★★ Online Courses to learn ★★★

★★★ Follow ★★★

DISCLAIMER: This video and description contains affiliate links, which means that if you click on one of the product links, I’ll receive a small commission. This help support the channel and allows us to continue to make videos like this. Thank you for the support!

[codeengineer]

Logic for Power of 2's
Fact: Any power of 2 minus 1 is all ones
ex: 8 is 1000 and 8-1=7 so 7 is 111
so the and operation returns 0
to check it's power of 2 just check if it's = 0
and if( n&(n-1)==0) return true;
:) thanks.

[sawvikdipto]

Thanks for this series. I was exactly looking for this type of video where I can test myself. I can do all the functions you have done but in brute force. So that would create a lot of problems. Thanks a lot sir.

[akku]

regarding cntbits() function. The logic of n & (n - 1) will fail for negative numbers coz as commented by Code Engineer, any power of 2 minus 1 is all one's ex: 8 is 1000 and 8-1=7 is 111 so the & operation returns 0. Conversely, it can also be said that it resets the last bit which equals 1. When inside a loop, it is like in each iteration the value of n gets reduced by 2^i, where i changes by i+1 in each iteration.
Note the difference by adding the following lines in the while loop.
print(f"n is now: {n}")
print(f"({n} & {n} - 1) is now: {n & (n - 1)}")
print(f"({n} & {n} - 1) in binary is: {bin(n & (n - 1))}")

[kalyanking]

you didnt explain logic for power of 2

[ΣυμεώνΜαστρακούλης]

def ispowerof2(n):
return not (n & ( n - 1))

this is a very simple code. Doesnt need the "and" operation with the n. If n is power of 2 on binary represation it will be if it is 2 on power of a then it will be 1 with a zeroes after. So n - 1 will be 11....111 with a ones. Then if you make the and operation (&) it will return 000...0000 with a + 1 zeros, the False boolean. You put the not operations so you will return True. In every other case the n and n -1 will have at least one common bit on the same positions and n & (n - 1) will return True so with the not it will return False

[epsitadas]

sir you did not explain the last topic that is to find single occuring element in an array

[siddharthsahu]

please explain the code kuch smajh nhi aya power of two

[Yagyaansh]

how does & operation work for negative numbers in python?? i am getting -8 on doing -8 & -7 ; -16 on doing -8 & -9

[UdayKiran-mwcr]

Bro please complete the course bro all are good

[quintrankid]

I'm a little confused about your function that tests for power of two. Why return x and y? Can't you just return y?