440,841 Members | 854 Online
Need help? Post your question and get tips & solutions from a community of 440,841 IT Pros & Developers. It's quick & easy.

# if (x && !(x & (x-1)) == 0)

 P: n/a Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? Thanks. Nov 15 '05 #1
20 Replies

 P: n/a "William" wrote in message news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca... Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? Wrong group. A hint anyway: think of binary representation of powers of 2 and not powers of 2. You'll see the answer. I stop here. Alex Nov 15 '05 #2

 P: n/a "Alexei A. Frounze" writes: "William" wrote in message news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca... Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? Wrong group. How is this the wrong group? A hint anyway: think of binary representation of powers of 2 and not powers of 2. You'll see the answer. I stop here. It's hard to understand what you mean by that. I *think* you mean Think of binary representation of powers of 2 and not powers of 2. but when I first read it I thought you were talking about "powers of 2 and not powers of 2", which doesn't make any sense. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #3

 P: n/a let x = 1000 (8, a power of 2); x-1 = 111 then x & (x-1) = 1111 !(x & (x-1)) = 0000 how does (1000 && 0000) == 0? On Sun, 14 Aug 2005, Keith Thompson wrote: "Alexei A. Frounze" writes: "William" wrote in message news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca... Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? Wrong group. How is this the wrong group? A hint anyway: think of binary representation of powers of 2 and not powers of 2. You'll see the answer. I stop here. It's hard to understand what you mean by that. I *think* you mean Think of binary representation of powers of 2 and not powers of 2. but when I first read it I thought you were talking about "powers of 2 and not powers of 2", which doesn't make any sense. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #4

 P: n/a "William" wrote in message news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca... let x = 1000 (8, a power of 2); x-1 = 111 then x & (x-1) = 1111 So, you don't even know how the operator & works. A point for you. !(x & (x-1)) = 0000 how does (1000 && 0000) == 0? And then you told yourself, there was x & (x-1), but not x && (x-1). You've got another point! How about reading a book on C or looking into some C reference? Alex Nov 15 '05 #5

 P: n/a "Keith Thompson" wrote in message news:ln************@nuthaus.mib.org... "Alexei A. Frounze" writes: "William" wrote in message news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca... Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? Wrong group. How is this the wrong group? The Q was about the algo. But the group is about the language. Isn't this what you want here, i.e. get the trolls and irrelevant Qs out? A hint anyway: think of binary representation of powers of 2 and not powers of 2. You'll see the answer. I stop here. It's hard to understand what you mean by that. I *think* you mean Think of binary representation of powers of 2 and not powers of 2. but when I first read it I thought you were talking about "powers of 2 and not powers of 2", which doesn't make any sense. Oh come on, you know what I meant. And it wasn't obviously some C operators like &,&& and !. If I had wanted to throw some C in, I'd have done that. Alex Nov 15 '05 #6

 P: n/a Alexei A. Frounze wrote: "Keith Thompson" wrote in message news:ln************@nuthaus.mib.org..."Alexei A. Frounze" writes:"William" wrote in messagenews:Pi******************************@cpu02.stu dent.cs.uwaterloo.ca...Original question:"Give a one-line C expression to test whether a numberis a power of 2. [No loops allowed - it's a simple test.]"Answer:if (x && !(x & (x-1)) == 0)My question:Why does this expression work?Wrong group.How is this the wrong group? The Q was about the algo. But the group is about the language. Isn't this what you want here, i.e. get the trolls and irrelevant Qs out? The question was how to implement a solution in C and it can be done in standard C without any non-standard libraries, so it's on topic. However, you may argue that it's off topic since the solution depends on the binary representation of integers. August Nov 15 '05 #7

 P: n/a akarl writes: Alexei A. Frounze wrote: "Keith Thompson" wrote in message news:ln************@nuthaus.mib.org..."Alexei A. Frounze" writes:"William" wrote in messagenews:Pi******************************@cpu02.st udent.cs.uwaterloo.ca...>Original question:>"Give a one-line C expression to test whether a number>is a power of 2. [No loops allowed - it's a simple test.]">>Answer:>if (x && !(x & (x-1)) == 0)>>My question:>Why does this expression work?Wrong group.How is this the wrong group? The Q was about the algo. But the group is about the language. Isn't this what you want here, i.e. get the trolls and irrelevant Qs out? The question was how to implement a solution in C and it can be done in standard C without any non-standard libraries, so it's on topic. However, you may argue that it's off topic since the solution depends on the binary representation of integers. The C standard specifies that integers are represented in binary. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #8

 P: n/a x & (x-1) = 0000 !(x & (x-1)) = 1 (since 0000 is just 0) (x && !(x & (x-1))) = 1000 && 1 = 1 therefore, if (x && !(x & (x-1)) == 0) returns false if x is a power of 2; true if x is NOT a power of 2. Can someone please verify for a newbie like me? Thanks. On Mon, 15 Aug 2005, Alexei A. Frounze wrote: "William" wrote in message news:Pi******************************@cpu02.studen t.cs.uwaterloo.ca... let x = 1000 (8, a power of 2); x-1 = 111 then x & (x-1) = 1111 So, you don't even know how the operator & works. A point for you. !(x & (x-1)) = 0000 how does (1000 && 0000) == 0? And then you told yourself, there was x & (x-1), but not x && (x-1). You've got another point! How about reading a book on C or looking into some C reference? Alex Nov 15 '05 #9

 P: n/a Keith Thompson wrote: "Alexei A. Frounze" writes:"William" wrote in messagenews:Pi******************************@cpu02.stud ent.cs.uwaterloo.ca...Original question:"Give a one-line C expression to test whether a numberis a power of 2. [No loops allowed - it's a simple test.]"Answer:if (x && !(x & (x-1)) == 0)My question:Why does this expression work?Wrong group. How is this the wrong group? Because your question has nothing to do with C. It is about the behavior of binary numbers.A hint anyway: think of binary representation of powers of 2 and not powersof 2. You'll see the answer. I stop here. It's hard to understand what you mean by that. I *think* you mean Think of binary representation of powers of 2 and not powers of 2. but when I first read it I thought you were talking about "powers of 2 and not powers of 2", which doesn't make any sense. Yes, it makes perfect sense. Since you need the push, I'll fill it out for you. Think about the representation of a power of 2: x: 0...000...010......0 and x-1: 0...000..001......1 x & (x-1) is then 0...000..000......0 == 0 Think about the representation of "not a power of 2" (and not zero), there will be at least two bits set in such a number: x: 0...010...010......0 and x-1: 0...010..001......1 x & (x-1) is then 0...010..000......0 != 0 Note that all ones in a "not a power of 2" except the rightmost one remains in x & (x-1). So you were indeed to think of the binary representation of "powers of 2" and "not powers of 2." Before you label things as not making any sense, consider that it might be that you have a cognitive shortcoming and that the thing does make sense to those who are willing to think about it. Nov 15 '05 #10

 P: n/a Martin Ambuhl writes: Keith Thompson wrote: "Alexei A. Frounze" writes:"William" wrote in messagenews:Pi******************************@cpu02.stu dent.cs.uwaterloo.ca...Original question:"Give a one-line C expression to test whether a numberis a power of 2. [No loops allowed - it's a simple test.]"Answer:if (x && !(x & (x-1)) == 0)My question:Why does this expression work?Wrong group. How is this the wrong group? Because your question has nothing to do with C. It is about the behavior of binary numbers. It wasn't my question. In any case, it's about the behavior of certain C operators (which happen to operate on binary numbers, which C requires). A hint anyway: think of binary representation of powers of 2 and not powersof 2. You'll see the answer. I stop here. It's hard to understand what you mean by that. I *think* you mean Think of binary representation of powers of 2 and not powers of 2. but when I first read it I thought you were talking about "powers of 2 and not powers of 2", which doesn't make any sense. Yes, it makes perfect sense. [snip] So you were indeed to think of the binary representation of "powers of 2" and "not powers of 2." Ok. If he had written "non powers of 2", it would have been easier to understand. My problem was with the poor wording of the statement, not with the underlying concepts. Before you label things as not making any sense, consider that it might be that you have a cognitive shortcoming and that the thing does make sense to those who are willing to think about it. Yeah, that must be it. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #11

 P: n/a In article , William wrote: Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? Write down exactly what happens in the expression when x is a power of two, then write down exactly what happens when x is not a power of two, then it is quite obvious. Nov 15 '05 #12

 P: n/a Keith Thompson wrote: akarl writes:Alexei A. Frounze wrote:"Keith Thompson" wrote in messagenews:ln************@nuthaus.mib.org... "Alexei A. Frounze" writes: >"William" wrote in message>news:Pi******************************@cpu02.s tudent.cs.uwaterloo.ca...>>>>Original question:>>"Give a one-line C expression to test whether a number>>is a power of 2. [No loops allowed - it's a simple test.]">>>>Answer:>>if (x && !(x & (x-1)) == 0)>>>>My question:>>Why does this expression work?>>Wrong group.How is this the wrong group?The Q was about the algo. But the group is about the language. Isn'tthiswhat you want here, i.e. get the trolls and irrelevant Qs out?The question was how to implement a solution in C and it can be donein standard C without any non-standard libraries, so it's on topic.However, you may argue that it's off topic since the solution dependson the binary representation of integers. The C standard specifies that integers are represented in binary. OK, in that case there is no question about it. August Nov 15 '05 #13

 P: n/a I think this is the right answer: if(test&&(test&(test-1))==0) printf("The number is the power of 2!\n"); else printf("The number is not the power of 2!\n"); Nov 15 '05 #14

 P: n/a Please do not top-post. Place your answer below or interspersed with the text you are replying to. William wrote: x & (x-1) = 0000 !(x & (x-1)) = 1 (since 0000 is just 0) (x && !(x & (x-1))) = 1000 && 1 = 1 therefore, if (x && !(x & (x-1)) == 0) returns false if x is a power of 2; true if x is NOT a power of 2. Can someone please verify for a newbie like me? Yep. Note that all bit operations should be performed only on unsigned types and that the explanation below only holds for nonnegative integers x. I would rather parse the whole thing in another way; please have a look at an operator precedence table of your choice: if (x && !(x & (x-1)) == 0) x && is equivalent to x!=0 && meaning x is a candidate for a power of two only if x is not zero. The following logical expression is only evaluated if x!=0. !(....) == 0 is equivalent to (....) != 0 or (....) x & (x-1) leaves all bits of x higher than (left of) the lowest (rightmost) set bit untouched and sets the rest to 0: Let x = bb..b10...0: bb..b10...0 - 1 is bb..b01...1 which becomes bb..b00...0 under x & (x-1). This means that for x!=0 the above is zero if bb..b is zero, i.e. if x contains exactly one set bit, i.e. if x is a power of two. So, if we want to test for powers of two, we need if (x && !(x & (x-1))) or if (x!=0 && (x & (x-1))==0) The original test tests for nonzero non-power-of-two x. Cheers Michael -- E-Mail: Mine is an /at/ gmx /dot/ de address. Nov 15 '05 #15

 P: n/a William wrote: Original question: "Give a one-line C expression to test whether a number is a power of 2. [No loops allowed - it's a simple test.]" Answer: if (x && !(x & (x-1)) == 0) My question: Why does this expression work? It doesn't. You have to drop the negation. Christian Nov 15 '05 #16

 P: n/a In article , William wrote: x & (x-1) = 0000 !(x & (x-1)) = 1 (since 0000 is just 0) (x && !(x & (x-1))) = 1000 && 1 = 1 therefore, if (x && !(x & (x-1)) == 0) returns false if x is a power of 2; true if x is NOT a power of 2. Can someone please verify for a newbie like me? Thanks. Yes, mostly. It seems to fail on the edge cases of 0 and the most negative int, e.g. -INT_MAX-1 or -2147483648 on a 2's complement machine with sizeof(int) == 4. However, the type of x was not stated and I assumed int. If one assumes it is an unsigned int then there is no problem with -INT_MAX-1. x==0 is still wrong, plus it's somewhat counter-intuitive for the expression to return false for "yes, it's a power of two" A better expression that fixes these two issues might be: if (x && (x & (x-1)) == 0) More disturbing of course is in many mathematical contexts in which powers of two are interesting, it's common for the range of the numbers involved to be larger than what will fit into an int. The bitwise trickery won't work on float or double, obviously. Nov 15 '05 #17

 P: n/a I don't think that works. There shouldn't be the ! in the expression and this will return true is x = 1, which obviously isn't correct. Nov 15 '05 #18

 P: n/a "ca***********@gmail.com" writes: I don't think that works. There shouldn't be the ! in the expression and this will return true is x = 1, which obviously isn't correct. You don't think *what* works? Don't assume your readers have easy access to the article to which you're replying. You can provide proper quotations and attributions through groups.google.com; search this newsgroup for advice (which has been offered hundreds of times. -- Keith Thompson (The_Other_Keith) ks***@mib.org San Diego Supercomputer Center <*> We must do something. This is something. Therefore, we must do this. Nov 15 '05 #19

 P: n/a On 2005-08-16 00:54:41 -0400, "ca***********@gmail.com" said: I don't think that works. There shouldn't be the ! in the expression and this will return true is x = 1, which obviously isn't correct. 2**0 == 1 -- Clark S. Cox, III cl*******@gmail.com Nov 15 '05 #20

 P: n/a Clark S. Cox III wrote: On 2005-08-16 00:54:41 -0400, "ca***********@gmail.com" said: I don't think that works. There shouldn't be the ! in the expression and this will return true is x = 1, which obviously isn't correct. 2**0 == 1 -- Clark S. Cox, III cl*******@gmail.com Yep, that will teach me to post after my bedtime. Of course 1 is a power of two; 2^0 = 1. Yikes, sorry about that. Nov 15 '05 #21

### This discussion thread is closed

Replies have been disabled for this discussion.