Calcudoku puzzle forum
https://www.calcudoku.org/forum/

Bitwise operator
https://www.calcudoku.org/forum/viewtopic.php?f=3&t=63
Page 1 of 2

Author:  jomapil  [ Tue Sep 20, 2011 10:57 am ]
Post subject:  Bitwise operator

Hi everyone.

I made some combinations and n| looks like n+ . But with good knowledge of this mathematics, at first sight, it's not so evident.

Please tell me if there is a rule to see easily if n| is even or odd.

In any case the number of possibilities with n| is greater or lesser than n+? Or there isn't an absolute rule about this?

Thank you for your explanation.

P.S. 3+ = 1+2 ( one hypothesis ) but
3| = 11|01 and 11|10 and 10|01 ( three hypothesis )

Is it always in this way?

Author:  honkhonk  [ Tue Sep 20, 2011 12:34 pm ]
Post subject:  Re: Bitwise operator

*Spoiler* <Don't read this if you want to figure the bitwise operator by yourself> *Spoiler*







I don't think there is an absolute rule. In case of a cage of 2 the combinations possible are limited though

For example: 5+=3+2, 4+1 but 5|= 41, 54, 51
6+=4+2, 5+1 but 6|= 46, 42, 26

Only 7| has a lot of combinations possible among which are 7x with x any number but 8

Does this help?

Author:  jomapil  [ Tue Sep 20, 2011 1:55 pm ]
Post subject:  Re: Bitwise operator

Sadly it seems there is no absolute rule. But if n| is even the cage is always even, but if n! is odd the cage can be odd or even.

Please anyone confirms if this is true.

I didn't understand what you want to say with 7| .
Thanks, honkhonk.

Author:  honkhonk  [ Tue Sep 20, 2011 3:23 pm ]
Post subject:  Re: Bitwise operator

What I meant is:

In a 2-cage situation 7| can be

71, 72, 73, 74, 75, 76 but also
61, 63, 65, 53, 52, 43

Just not the number 8.

I think you're looking for a rule you don't really need to solve the bitwise operator puzzles

If you say n| is even then the 2-cage is even, you are right since 6| is 42, 64 and 62; 10| is 82, 12| is 84 and 14| is 86
If you say n| is odd then the 2-cage is odd or even you say the 2-cage can be anything which is right

1|, 2|, 4|, 8| don't exist so you don't need them. This leaves 3|, 5| an 6| with each 3 possibilities and 7| with 10 possibillities. The n| 2-cages with n>7 contain an 8 and n-8.

So try first to locate 2-cages with n>7, they are easy to solve. Next try regular cages with no | operator or try cages with limited possibilities like 5|, 3| and 6|. You can also solve 7| cages provided you know there is no 7 in the solution or you know more numbers in the column/row (then the possibillities are limited).


In general:
The general rule with binary numbers is that any decimal number that is odd, in binary representation has a last bit set to 1 (1=001, 5=101 etc) (Decimal numbers that are even have a last bit set to 0) When you apply the bitwise OR operator to two operands of which at least one is odd the value of this last bit will always be 1. Because if you have the numbers **1 and *** on which you use the bitwise OR operation the last bit '1 or *' = 1 no matter what the value of *.

Hence if you want the bitwise OR to have an even result (6|, 8| etc) BOTH operands must be even (last bit set to 0). Thus for any cage n| with n even both numbers must be even, for n| odd at least one number must be odd.

Truth table of the OR operand:

0|0 = 0
1|0= 1
0|1 = 1
1|1 = 1

When this is the last bit it transalates to:
even|even = even
odd|even = odd
even|odd = odd
odd|odd = odd

Author:  jomapil  [ Tue Sep 20, 2011 4:14 pm ]
Post subject:  Re: Bitwise operator

OK honkhonk.

You avoided I did those calculus. So the great difficulty is only the 7| .

I only didn't understand why you say 7| has 10 possibilities and those possibilities are 71, 72, 73, 74, 75, 76 but also
61, 63, 65, 53, 52, 43

a total of 12.

Thank you very much.

Author:  honkhonk  [ Tue Sep 20, 2011 4:23 pm ]
Post subject:  Re: Bitwise operator

My mistake, should be 12.

Clm: you're also right. I corrected it....


I'm not that good with numbers ;-)

greetz,
HonkHonk

Author:  clm  [ Tue Sep 20, 2011 8:22 pm ]
Post subject:  Re: Bitwise operator

honkhonk wrote:

I don't think there is an absolute rule. In case of a cage of 2 the combinations possible are limited though

For example: 5+=3+2, 4+1 but 5|= 41, 24, 12
6+=4+2, 5+1 but 6|= 46, 42, 26

Only 7| has a lot of combinations possible among which are 7x with x any number but 8

Does this help?


honkhonk, I think there is a little mistake in 5| = 41, 24, 12; it must be 5| = 41, 45, 15, a 2 is not valid inside a cage 5| since it activates bit number 2. Your explanation about the 12 combinations for 7| is very clear, as well as the analysis with the parity.

jomapil, you may observe that 53 and 75 (valid for 7| produce an even cage). The parity itself, as the addition itself, is not very useful when we have the operation bitwise OR|, only perhaps when finalizing the puzzle. If we have a three cells cage (L-shape), the number of combinations increase dramatically (see my post "Searching for the operands" where I detailed the 56 possibilities for an L-shape 3-cells cage in the case of 7|).

It is better, in my opinion, just converting the possible operands to binary, apply the OR to the binary words and check the result, or inversely, eliminating numbers that "can not be present" (as the 8 in cages n| where n < 8, or the 7 in cages n| where n < 7, ...). For instance, 15| in a 3-cell L-shaped cage may have 8 and the 12 combinations shown by honkhonk, but also 8-8-7, 7-7-8... . With practice it will become easy, and useful for all situations, think in a 3-cells cage "in line" for instance (not very frequent in the calcudokus on tuesdays).

My recommendation is playing with all this simply filling the cages in the puzzle and observing the response of the "continuous error checking" telling you in red the forbidden combinations.

Author:  jomapil  [ Tue Sep 20, 2011 9:51 pm ]
Post subject:  Re: Bitwise operator

clm, you are right. 2 can't be inside a cage 5|. We must change 2 for 5.

But 53 and 75 don't produce an even cage. You were right if it was XOR. But with OR it's enough one of the operators be odd and the result is an odd cage.

Author:  clm  [ Wed Sep 21, 2011 12:27 am ]
Post subject:  Re: Bitwise operator

jomapil wrote:
clm, you are right. 2 can't be inside a cage 5|. We must change 2 for 5.

But 53 and 75 don't produce an even cage. You were right if it was XOR. But with OR it's enough one of the operators be odd and the result is an odd cage.


I usually refer to an "even" cage when the sum of the numbers inside is even, so 5 + 3 = 8 and 7 + 5 = 12, would produce an "even" cage, also 71 and 73 (among the 12 combinations for the 7| in two cells referred by honkhonk) that also produce a 7| (in case of the bitwise OR) are cages "even". All this talking about the "parity" of the cage, in order to use it for the "parity" rule. That is the "paradox"; another case, i.e., with 5|, the combination 15 produces an "even" cage, while 14 and 45 (both valid) are "odd" cages. Obviously in a cage n| where n is even, the cage itself is even since all numbers inside must be even (the last bit is a zero because if any of the numbers were odd its last bit would be 1 and would set to 1 the last bit of the result of "ORing" all the numbers), and the sum even (finished in zero) as well explained by honkhonk. Consequently, the uncertainty with the parity of the cage only appears when, in a cage n|, n is odd because now the "cage" itself can be odd or even; more examples: for a 15| in a 3-cells L-shaped cage, 8-8-7 (total of 23, odd) or 8-7-7 (total of 22, even) are valid combinations; in the case of a cage 13|, 8-1-5 (total of 14, even) and 8-4-5 (total of 17, odd) are also valid combinations (here, thus, we can see that the arithmetical value of the sum has nothing to do with the result of the bitwise OR operation, a total of 23, for instance, for a cage 15|).
The XOR, of course, is a different logic operation for the binary words, but for the moment we do not have it.

Author:  jomapil  [ Wed Sep 21, 2011 8:14 am ]
Post subject:  Re: Bitwise operator

Hi, clm.
You are right, of course. At first I understood your statement of a different way. In one of my replies to this thread I say:
" But if n| is even the cage is always even, but if n! is odd the cage can be odd or even."

exactly what you said.

Another point refers to the n| cages of 3-cells: In my first solved problem with bitwise OR ( 20Sep2011-8x8 difficult ) I didn't need what I'm going to tell you because I solved these 3-cages in another way. But, on the whole, I eventually need to calculate great number of results ( 7| has, theoretically, 7^3 hypothesis, if I'm not wrong! ). Anyway we must calculate them? Or is there any secrets I don't know?

Best regards.

P.S. - As you see I'm not a great expert of English language, but I hope you understand me in the essencial.

Page 1 of 2 All times are UTC + 1 hour [ DST ]
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group
http://www.phpbb.com/