Your mission, should you choose to accept it..
-
.. 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?if((a * b * c) == 0)The clue was in the||s. -
if((a * b * c) == 0)The clue was in the||s.a=0 b=2 c=0
harold aproot wrote:
which is a nice try but tests whether all of them are zero instead of any of them
[edit] ouch, misread. :-O
Oxfords English < Official CCC Players Dictionary Excuse me for my improper grammar and typos. It's because English is my primary language, not my first language. My first languages are C# and Java. VB, ASP, JS, PHP and SQL are my second language. Indonesian came as my third language. My fourth language? I'm still creating it, I'll let you know when it's done! :-D
-
.. 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:
which is wrong in general, bonus points if you know why
Overflow could cause multiple non-zero values to appear to equal zero?
-
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.
} -
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) { }
