+ 8

[CHALLENGE] Power Of Two

The challenge is quite simple ... You'll have to do a function that tells whether or not a number (the input) is a power of two. But beware ! Two criteria will be judged as the challenge is easy in itself. Your function will have to be AS OPTIMIZED AS POSSIBLE and AS SHORT AS POSSIBLE. Good luck :)

19th Aug 2017, 8:12 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
28 odpowiedzi
+ 7
x & (x - 1) == 0
19th Aug 2017, 8:20 PM
Roman
Roman - avatar
19th Aug 2017, 8:41 PM
MizoPro
MizoPro - avatar
+ 7
@sayan, a number of two is binary written as looots of 0s, and one and only one number 1, wherever in the number. So if you reduce it by 1, it will have no common bits with its past self Examples : 8 : 1000 & 0111 = 0000 7 : 0111 & 0110 = 0110 6 : 0110 & 0101 = 0100 @Roman, reaaaaally nice !
19th Aug 2017, 8:31 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 4
here you go! hope you like it! https://code.sololearn.com/cocQa8N0gEG7/#cpp
19th Aug 2017, 8:39 PM
Luca
Luca - avatar
19th Aug 2017, 8:33 PM
sayan chandra
sayan chandra - avatar
+ 3
@sayan, nice but log is expensive
19th Aug 2017, 8:35 PM
Baptiste E. Prunier
Baptiste E. Prunier - avatar
+ 3
@sayan i like your idea in version 2 👍👍👍
19th Aug 2017, 9:10 PM
Luca
Luca - avatar
+ 2
baptiste please explain that & thing up there . idk that
19th Aug 2017, 8:27 PM
sayan chandra
sayan chandra - avatar
+ 2
It's "and" bitwise operation. All numbers that are powers of two has only one 1 bit. & (x - 1) remove this bit, so result will be 0.
19th Aug 2017, 8:31 PM
Roman
Roman - avatar
+ 2
19th Aug 2017, 9:07 PM
sayan chandra
sayan chandra - avatar
+ 1
x-1 and & are single instructions at machine level. floating log and int<>float conversion are 100x more expensive
19th Aug 2017, 8:38 PM
VcC
VcC - avatar
+ 1
https://code.sololearn.com/cbxAg0Yv6Dav/?ref=app i wish i knew the bitwise thing! not very optimized but here my try on this
20th Aug 2017, 4:43 PM
MGlossCode
MGlossCode - avatar
0
@Baptiste Here is the answer for q^p for any q: http://cr.yp.to/papers/powers.pdf
20th Aug 2017, 5:13 AM
VcC
VcC - avatar
0
if p&(p-1)==0 is the fastest way to see if p is a pure power of two
20th Aug 2017, 5:32 AM
VcC
VcC - avatar
0
ooh... ya but brother i did not know that thing that binary operator... baptiste yesterday explained me
20th Aug 2017, 5:33 AM
sayan chandra
sayan chandra - avatar
- 1
vcc baptiste its my 4 th version in python it can calculate up to "3 lakh " yes check it out https://code.sololearn.com/cT5WxLWt9jIk/?ref=app
20th Aug 2017, 5:21 AM
sayan chandra
sayan chandra - avatar
- 1
3 lakh .... more more more
20th Aug 2017, 5:23 AM
sayan chandra
sayan chandra - avatar
- 1
Good ! You can use integer div for k (//)
20th Aug 2017, 5:25 AM
VcC
VcC - avatar
- 1
What is a lakh ?
20th Aug 2017, 5:26 AM
VcC
VcC - avatar
- 1
3 lakh=300k
20th Aug 2017, 5:26 AM
sayan chandra
sayan chandra - avatar