Your mission, should you choose to accept it..
-
Point awarded :) Very good. I had a different one though, that used fewer operations, can you find that one?
No problem, same principle, now taking advantage of the product having a limited number of factors:
h(x) = (x | x>>8 | x>>16 | x>>24) & 0xFF
and
if ( h(a)*h(b)*h(c) == 0)...:)Luc Pattyn [My Articles] Nil Volentibus Arduum
-
.. is to write a replacement for
if (a == 0 || b == 0 || c == 0), that - uses at most one comparison. - uses only integer arithmetic. - does not make assumptions about the values of a b and c, except that they are 32-bit 2's complement integers. This entirely useless challenge (is there any other kind?) was inspired by a question on a site that shall not be named, asking for a shorter way to write it. But then people started answering witha * b * c == 0(which is wrong in general, bonus points if you know why) and(a | b | c) == 0which is a nice try but tests whether all of them are zero instead of any of them. That inspired me to search for a solution like that, and I found 2, one of which uses only basic operators. Can you find it?bloody hell. (a & b & c) == 0 ?
-
bloody hell. (a & b & c) == 0 ?
-
it won't work :)
-
No problem, same principle, now taking advantage of the product having a limited number of factors:
h(x) = (x | x>>8 | x>>16 | x>>24) & 0xFF
and
if ( h(a)*h(b)*h(c) == 0)...:)Luc Pattyn [My Articles] Nil Volentibus Arduum
-
due to overflow a*b*c may result in false zeroes when a power of 2 aliases to zero (say a=2^16, b=2^16, c=1) For 32-bit integers the function
f(x) = x | x>>1 | x>>2 | ... | x>>31
calculates the next power of 2 minus 1, resulting in a non-zero and odd number for all non-zero integers. (add terms for wider integers, and add parentheses if you must). therefore f(a)*f(b)*f(c) is zero if and only if a*b*c is zero, and it doesn't suffer from overflow aliasing, as the lowest bit gets preserved by multiplication. BTW: To completely avoid overflow, one could also use
g(x) = f(x) & 1
:)
Luc Pattyn [My Articles] Nil Volentibus Arduum
If we can use assembly instructions, we can compact your code using BSR or BSF. :)
-
If we can use assembly instructions, we can compact your code using BSR or BSF. :)
-
12? that is a lot. Lets use the sign bit now:
if ( (a|-a)&(b|-b)&(c|-c) < 0 ) log("all non-zero");
:-D
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
No problem, same principle, now taking advantage of the product having a limited number of factors:
h(x) = (x | x>>8 | x>>16 | x>>24) & 0xFF
and
if ( h(a)*h(b)*h(c) == 0)...:)Luc Pattyn [My Articles] Nil Volentibus Arduum
I think that since the cube root of Int32.MaxValue is greater than 1024, we can further reduce it using your same technique (10-bit chunks instead of 8-bit chunks):
if (((a | (a << 10) | (a << 20)) & 0xFF7) * ((b | (b << 10) | (b << 20)) & 0xFF7) * ((c | (c << 10) | (c << 20)) & 0xFF7) == 0) { }
-
12? that is a lot. Lets use the sign bit now:
if ( (a|-a)&(b|-b)&(c|-c) < 0 ) log("all non-zero");
:-D
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
I think that since the cube root of Int32.MaxValue is greater than 1024, we can further reduce it using your same technique (10-bit chunks instead of 8-bit chunks):
if (((a | (a << 10) | (a << 20)) & 0xFF7) * ((b | (b << 10) | (b << 20)) & 0xFF7) * ((c | (c << 10) | (c << 20)) & 0xFF7) == 0) { }
Actually, I think bit shifting might do funny things depending on the sign bit, so instead of shifting by 20, might just want to shift by 14.
-
I think that since the cube root of Int32.MaxValue is greater than 1024, we can further reduce it using your same technique (10-bit chunks instead of 8-bit chunks):
if (((a | (a << 10) | (a << 20)) & 0xFF7) * ((b | (b << 10) | (b << 20)) & 0xFF7) * ((c | (c << 10) | (c << 20)) & 0xFF7) == 0) { }
That technique is so outdated now. :laugh:
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
That technique is so outdated now. :laugh:
Luc Pattyn [My Articles] Nil Volentibus Arduum
Yep. :rolleyes:
-
:jig:
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
12? that is a lot. Lets use the sign bit now:
if ( (a|-a)&(b|-b)&(c|-c) < 0 ) log("all non-zero");
:-D
Luc Pattyn [My Articles] Nil Volentibus Arduum
Well done. :thumbsup:
-
Well done. :thumbsup:
Thanks. The nice thing about this approach is it works for all widths, and for any number of product factors, as long as they are all signed integers. :)
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
12? that is a lot. Lets use the sign bit now:
if ( (a|-a)&(b|-b)&(c|-c) < 0 ) log("all non-zero");
:-D
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
.. is to write a replacement for
if (a == 0 || b == 0 || c == 0), that - uses at most one comparison. - uses only integer arithmetic. - does not make assumptions about the values of a b and c, except that they are 32-bit 2's complement integers. This entirely useless challenge (is there any other kind?) was inspired by a question on a site that shall not be named, asking for a shorter way to write it. But then people started answering witha * b * c == 0(which is wrong in general, bonus points if you know why) and(a | b | c) == 0which is a nice try but tests whether all of them are zero instead of any of them. That inspired me to search for a solution like that, and I found 2, one of which uses only basic operators. Can you find it?harold aptroot wrote:
entirely useless challenge (is there any other kind?)
Some of these wouldn't be called entirely useless, would they? :) PS: the damn link-paste bug is acting up again.
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
harold aptroot wrote:
entirely useless challenge (is there any other kind?)
Some of these wouldn't be called entirely useless, would they? :) PS: the damn link-paste bug is acting up again.
Luc Pattyn [My Articles] Nil Volentibus Arduum
-
Aren't they just some other kind of useless? The kind of useless where you won't solve the challenge anyway so why bother.. But you have a point
When everything were useless, then so would be the word itself. :)
Luc Pattyn [My Articles] Nil Volentibus Arduum