Your mission, should you choose to accept it..
-
harold aptroot wrote:
which is wrong in general, bonus points if you know why
Overflow could cause multiple non-zero values to appear to equal zero?
-
.. 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?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
-
.. 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:
a * b * c == 0(which is wrong in general, bonus points if you know why)[edit]Sh*t! Too late for the party :( [/edit]
-
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
-
.. 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?Pfft, I don't even need a comparison:
try
{
int x = 1 / a / b / c;
}
catch (DivideByZeroException)
{
// One of them was zero.
} -
harold aptroot wrote:
a * b * c == 0(which is wrong in general, bonus points if you know why)[edit]Sh*t! Too late for the party :( [/edit]
-
Pfft, I don't even need a comparison:
try
{
int x = 1 / a / b / c;
}
catch (DivideByZeroException)
{
// One of them was zero.
}My thought exactly! I don't think Harold would approve of it though :laugh:
It's an OO world.
public class Naerling : Lazy<Person>{
public void DoWork(){ throw new NotImplementedException(); }
} -
Pfft, I don't even need a comparison:
try
{
int x = 1 / a / b / c;
}
catch (DivideByZeroException)
{
// One of them was zero.
} -
.. 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 ?
-
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
-
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) { }
That technique is so outdated now. :laugh:
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.
