4/5 In one line, how do you determine if X is a power of 2? If you already
know the answer, please don't answer.
\_ echo "is X a power of 2?" > mail mrsmartguy@hostname.berkeley.edu
\_ In one line of what? If it's one line of C code, I just figured out
the answer.
\_ One line doesn't mean what you think it means.
\_ bool power_of_2 = (x == 1) ? true : (x == 2) ? true : (x == 4) ?
true : (x == 8) ? true : (x == 16) ? true : (x == 32) ? true : (x ==
64) ? true : (x == 128) ? true : (x == 256) ? true : (x == 512) ?
true : (x == 1024) ? true : (x == 2048) ? true : (x == 4096) ? true
: (x == 8192) ? true : (x == 16384) ? true : (x == 32768) ? true :
(x == 65536) ? true : (x == 131072) ? true : (x == 262144) ? true :
(x == 524288) ? true : (x == 1048576) ? true : (x == 2097152) ? true
: (x == 4194304) ? true : (x == 8388608) ? true : (x == 16777216) ?
true : (x == 33554432) ? true : (x == 67108864) ? true : (x ==
134217728) ? true : (x == 268435456) ? true : (x == 536870912) ?
true : (x == 1073741824) ? true : (x == 2147483648) ? true : false;
\_ Are you assuming a certain number of bits in an integer?
\_ Both solutions are nonportable.
\_ Yes. I'm mocking the person asking the question. His
question doesn't have an answer.
\_ (f && (!(f & (f-1))))
And a better way to ask this question is can you
determine if a number is a power of two in O(1) time.
\_ None of your operations are truly O(1).
A naive solution like doing a bunch of & operations
is just as O(1) by your criteria.
\_ In modern processors all 3 operations
( &, &&, and -) are constant time.
That makes it O(1). The naive solution on the
other hand is O(n) where n is the number of bits
in an integer. If you double the width of the
integer the time to check doubles. That's not
O(1) in any way shape or form.
\_ That's my point. Those operations are only
constant time up to a certain number of bits.
After that it's going to cost you, e.g. with
bigints.
\_ By the same reasoning, lg(n)<64 so it's constant
time as well.
\_ I think it is pretty obvious you don't
understand bigO notation.
\_ So you're assuming unsigned and twos-complement?
\_ If it's unsigned, it wouldn't be two's complement,
would it?
\_ That's what I was looking for but I'm curious if there
are smart ways to do it in other languages. -op
\_ I'm assuming unsigned. f>0 is a simple signed check.
Twos complement isn't an assumption, as negative
numbers aren't ever an issue.
\_ -2147483648 is not a power of 2.
\_ ((f > 0) && (!(f & (f-1)))) -- !PP
\_ power_of_2 = (rindex(sprintf(%b, x),'1')==1) ? true : false;
assuming I put the parenthesis in the right place and x>1?
of course, I'm a tard and don't really understand bitwise ops.
\_ Ugh, why do people write "boolExpr ? true : false"? It's
redundant. Is "(boolExpr ? true : false) ? true : false" even
clearer for you?
\_ I suspect your solution doesn't actually work.
\_ Is it safe to say that any solution will take O(n) time considering
an arbritary number of bits?
\_ I suspect so, but I'm not sure --person who gave O(1) forumla above |