Berkeley CSUA MOTD:Entry 37070
Berkeley CSUA MOTD
 
WIKI | FAQ | Tech FAQ
http://csua.com/feed/
2017/11/22 [General] UID:1000 Activity:popular
11/22   

2005/4/5 [Science, Politics] UID:37070 Activity:very high
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
2017/11/22 [General] UID:1000 Activity:popular
11/22   

You may also be interested in these entries...
2012/3/19-6/4 [Science/GlobalWarming] UID:54344 Activity:nil
3/19    "Solar power station in Spain works at night"
        http://www.csua.org/u/vtm (news.yahoo.com)
	...
2010/12/15-2011/2/19 [Science/Electric, Politics/Foreign/Europe] UID:53983 Activity:nil
12/15   I'm planning on traveling to Europe and I was wondering if there's
        any reason I shouldn't be able to use a US power tap/strip (no surge
        suppression) with just a plug adaptor (i.e., no voltage conversion).
        This would be for use with electronics that accept 100V-240V. While
        the power strip is intended for use at 120V, it's just wires, right?
        (Also, this power strip has no power LED or similar.) If anything,
	...
2013/3/13-5/10 [Politics/Foreign/Asia/China] UID:54625 Activity:nil
3/13    "China's Drone Swarms Rise to Challenge US Power"
        http://www.csua.org/u/zgz (news.yahoo.com)
        Before our drones dominate the sky, we are already losing dominance.
	...
2012/11/6-12/18 [Politics/Domestic/California, Politics/Domestic/Election] UID:54524 Activity:nil
11/6    Four more years!
        \_ Yay! I look forward to 4 more years of doing absolutely nothing.
           It's a much better outcome than the alternative, which is 4 years
           of regress.
           \_ Can't argue with that.
        \_ Massachusetts went for Obama even though Mitt Romney was its
	...
2010/8/29-9/30 [Politics/Domestic/California, Politics/Domestic/Immigration] UID:53942 Activity:kinda low
8/29    OC turning liberal, maybe there is hope for CA afterall:
        http://www.nytimes.com/2010/08/30/us/politics/30orange.html
        \_ and the state is slowly turning conservative. Meg 2010!
           \_ We will see. Seems unlikely.
        \_ Yeah, because CA sure has a problem with not enough dems in power!
           If only dems had been running the state for the last 40 years!
	...
2010/5/26-6/30 [Politics/Foreign/Asia/China] UID:53845 Activity:nil
5/26    "China could join moves to sanction North Korea"
        http://news.yahoo.com/s/ap/20100526/ap_on_re_as/as_clinton_south_korea
        How did Hillary manage to do that when we're also asking China to
        concede on the economic front at the same time?
         \_ China doesn't want NK to implode. NK is a buffer between SK and
            China, or in other words a large buffer between a strong US ally and
	...
2010/4/28-5/10 [Politics/Domestic/President/Bush] UID:53808 Activity:nil
4/28    Laura Bush ran a stop sign and killed someone in 1963:
        http://www.nytimes.com/2010/04/28/books/28laura.html?no_interstitial
        How come she didn't go to jail?
        \_ Car drivers rarely go to jail for killing people.  -tom
        \_ Ted Kennedy killed a girl. Dick Cheney shot a man.
        \_ Ted Kennedy killed a girl. Hillary and Dick Cheney both shot a man.
	...
2010/2/22-3/30 [Politics/Foreign/MiddleEast/Iraq] UID:53722 Activity:nil
2/20    Ok serious question, NOT political.  This is straight up procedural.
        Has it been declared that we didn't find WMD in iraq? (think so).
        So why did we go into iraq (what was the gain), and if nobody really
        knows, why is nobody looking for the reason?
        \_ Political stability, military strategy (Iran), and to prevent
           Saddam from financing terrorism.
	...