Juts Posted January 28, 2009 Share Posted January 28, 2009 I've been trying to work out this problem for quite a long time. If anyone has any input, please help :p it should return 0 if x is anything other than 0, and 1 if x is 0. /* * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int bang(int x) { x =; return x; } Link to comment Share on other sites More sharing options...
0 Bazenga Posted January 28, 2009 Share Posted January 28, 2009 Hint: Number XOR self = 0, always. X ^ X = 0. Link to comment Share on other sites More sharing options...
0 Juts Posted January 28, 2009 Author Share Posted January 28, 2009 Hint: Number XOR self = 0, always. X ^ X = 0. To be honest, doesn't seem to help. Its obvious that x^x will always be 0. That doesn't check the value of x even a little. Link to comment Share on other sites More sharing options...
0 ViZioN Posted January 28, 2009 Share Posted January 28, 2009 To be honest, doesn't seem to help. Its obvious that x^x will always be 0. That doesn't check the value of x even a little. XOR it with 0 then. int bang(int x) { if ((x ^ 0) == 0){ return 1; }else{ return 0; } } edit: Simpler code int bang(int x) { return ((x ^ 0) == 0); } I'm tired :p This returns 1 if x = 0 and 1 if not. Link to comment Share on other sites More sharing options...
0 Andre S. Veteran Posted January 28, 2009 Veteran Share Posted January 28, 2009 I think his idea is to avoid using an if statement, but I feel like that's a bit too much of head scratching for saving 3 lines of code. Unless this needs to called a billion times per second, it shouldn't make any performance difference either. Link to comment Share on other sites More sharing options...
0 ViZioN Posted January 28, 2009 Share Posted January 28, 2009 Yeah that was the quick and dirty way I thought of doing it. Can be done in one line though, although as you say, it probably won't make any difference speed wise. Could always make it inline if it really mattered too. Link to comment Share on other sites More sharing options...
0 Bazenga Posted January 28, 2009 Share Posted January 28, 2009 Well, it's not a "problem" if we can use if statement. It doesn't make any sense! Link to comment Share on other sites More sharing options...
0 Mike Posted January 29, 2009 Share Posted January 29, 2009 XOR it with 0 then. int bang(int x) { if ((x ^ 0) == 0){ return 1; }else{ return 0; } } edit: Simpler code int bang(int x) { return ((x ^ 0) == 0); } I'm tired :p This returns 1 if x = 0 and 1 if not. even simpler! int bang(int x) { return (x == 0) ? 1 : 0 } but that defeats the purpose of the question Link to comment Share on other sites More sharing options...
0 cx323 Posted January 29, 2009 Share Posted January 29, 2009 int bang(int x) { int xsign = x>>31; int negxsign = ((~x)+1)>>31; return (~(xsign|negxsign))&1; } Link to comment Share on other sites More sharing options...
0 MrA Posted January 29, 2009 Share Posted January 29, 2009 (edited) Here's another one that's very easy to understand, and it's exactly 12 ops: int bang(int x) { x = x | (x >> 16); x = x | (x >> 8); x = x | (x >> 4); x = x | (x >> 2); x = x | (x >> 1); x = x & 0x00000001; return x ^ 1; } EDIT: Using a lookup table will eliminate a few ops. Edited January 29, 2009 by MrA Link to comment Share on other sites More sharing options...
0 hdood Posted January 29, 2009 Share Posted January 29, 2009 I think his idea is to avoid using an if statement, but I feel like that's a bit too much of head scratching for saving 3 lines of code. Unless this needs to called a billion times per second, it shouldn't make any performance difference either. There is no real point to the code other than learning. It's a homework question. Link to comment Share on other sites More sharing options...
0 adsadsads Posted January 29, 2009 Share Posted January 29, 2009 __inline BOOL bang(__in int iValue) { return x == 0; } It would probably assemble like this: neg rax sbb rax, rax inc rax Link to comment Share on other sites More sharing options...
0 hdood Posted January 29, 2009 Share Posted January 29, 2009 __inline BOOL bang(__in int iValue) { return x == 0; } You're doing a comparison, which isn't allowed. Link to comment Share on other sites More sharing options...
0 GreenMartian Posted January 29, 2009 Share Posted January 29, 2009 int bang(int x) { int xsign = x>>31; int negxsign = ((~x)+1)>>31; return (~(xsign|negxsign))&1; } Beat me to it. This seems to be the shortest solution (that uses only the legal ops mentioned in the post). It relies on the fact that ZERO is the only number with identical sign in its +ve and -ve form (both are zero). (sign | negsign) will be 0 for zero, and 1 for any other numbers. Flipping it, then and-ing it with 1 will give you the desired result. Link to comment Share on other sites More sharing options...
0 ekw Posted January 29, 2009 Share Posted January 29, 2009 (edited) *edit* whoops didnt read legal ops xD Edited January 29, 2009 by ekw Link to comment Share on other sites More sharing options...
Question
Juts
I've been trying to work out this problem for quite a long time. If anyone has any input, please help :p
it should return 0 if x is anything other than 0, and 1 if x is 0.
/* * bang - Compute !x without using ! * Examples: bang(3) = 0, bang(0) = 1 * Legal ops: ~ & ^ | + << >> * Max ops: 12 * Rating: 4 */ int bang(int x) { x =; return x; }Link to comment
Share on other sites
14 answers to this question
Recommended Posts