View unanswered posts | View active topics It is currently Thu Mar 28, 2024 2:26 pm



← Back to the Calcudoku puzzle page




Reply to topic  [ 11 posts ]  Go to page 1, 2  Next
 Bitwise AND 
Author Message

Posted on: Sat Jun 02, 2018 8:36 am




Posts: 87
Joined: Fri Jan 13, 2017 2:51 pm
Post Bitwise AND
I think the page with help for exotic operators (mod and bitwise OR, on viewtopic.php?f=3&t=84) needs updating, to include the bitwise AND operator. The new operator can be a bit puzzling for relatively inexperienced solvers.


Profile

Posted on: Sun Jun 03, 2018 4:57 am




Posts: 931
Location: Ladysmith, BC, Canada
Joined: Fri May 13, 2011 1:37 am
Post Re: Bitwise AND
HOW TRUE [confused]......tried solving just the puzzle without the bitwise parts and did solve it but then when I entered the numbers a couple were incorrect on the bitwise side.....so my solution was not a correct solution......wish there was a chart for the bitwise and operation like the chart for the bitwise or operation


Profile
User avatar

Posted on: Sun Jun 03, 2018 10:33 am




Posts: 3296
Joined: Thu May 12, 2011 11:58 pm
Post Re: Bitwise AND
Check out these pages:

https://en.wikipedia.org/wiki/Bitwise_operation

http://wiki.schoolcoders.com/gcse/data- ... perations/


And this one is insane:

http://rosettacode.org/wiki/Bitwise_operations [scared]

severe OCD page [lol]


Profile

Posted on: Sun Jun 03, 2018 4:20 pm




Posts: 691
Joined: Wed Apr 16, 2014 9:20 pm
Post Re: Bitwise AND
Bitwise And : One will have to use Binary, just as one does for Bitwise Or

To have a bit turned on (= 1) represented in the final answer, every number in the cage must have that bit turned on (= 1)

(6,7) & = 6
110
111
110

(2,5) & = 0
010
101
000

(3, 5, 7) & = 1
011
101
111
001


Profile

Posted on: Sun Jun 03, 2018 10:02 pm




Posts: 931
Location: Ladysmith, BC, Canada
Joined: Fri May 13, 2011 1:37 am
Post Re: Bitwise AND
This is definitely beyond my cognitive "powers"......I have no clue how 0's and 1's in any combination can give me a 3 cell cage amounting to 15 [sad] [sad] [sad] !!!!


Profile

Posted on: Mon Jun 04, 2018 5:34 am




Posts: 691
Joined: Wed Apr 16, 2014 9:20 pm
Post Re: Bitwise AND
Beaker,
As I am looking at Marble's puzzle there is no 3 cell & = 15.

There are a few multi cell | =15. (Bitwise Or)

This puzzle has both Bitwise And & and Bitwise Or |. It is tricky. You have to switch your binary thinking depending on the operator. Otherwise, PM me.

(Hint: 8 must be one of the numbers in the bitwise Or = 15 cage as it is the only possibility to get the left most bit turned on)


Profile

Posted on: Mon Jun 04, 2018 9:14 am




Posts: 135
Joined: Tue Apr 24, 2012 7:47 pm
Post Re: Bitwise AND
Hi, beaker. I just wanted to add some more clarification for the bitwise AND operator. Firstly, we've gotta know how to write a target number in binary code. We'll use the numbers 20 and 25 as examples, and it's a good idea to number each of our steps as we go along.

So, how do we write 20 in binary code, anyhow? We divide the number in question by 2, and see whether our remainder is 0 or 1. Then we take the number we got in the previous step and divide THAT by 2, again checking whether our remainder is 0 or 1. This process continues until we can't divide by 2 anymore. Now, it's time to put my explanation into action - here goes.

How to write 20 in binary code.....

Step 1: We divide 20 by 2 to get a result of 10 and a remainder of 0.
Step 2: Now we divide our previous result, 10, by 2 to obtain 5 and a remainder of 0.
Step 3: 5 gets divided by 2; result is 2 and remainder is 1.
Step 4: 2 divided by 2 is 1; remainder 0.
Step 5: 1 cannot be divided by 2; this is the end of the line. Our result is 0 and our remainder is 1.

Now that we've obtained our remainders for each step, we have to reverse our sequence to get the binary representation of 20.

Step 5 = 1
Step 4 = 0
Step 3 = 1
Step 2 = 0
Step 1 = 0

So, the binary representation of 20 is 1 0 1 0 0.

Now, I'll demonstrate how to convert a binary string into a decimal number. To do that, we need to count how many digits that string has. In the example above, we've got 5 digits. The leftmost digit is always 2 raised to however many digits are in the string minus 1. That is, the leftmost digit is 1 x (2^4). On the other hand, the rightmost digit is always either 0 or 1 times 2 raised to the 0. That said, I'll now explain how in Beelzebub's basement this string gives a result of 20.

1 x (2^4) + 0 x (2^3) + 1 x (2^2) + 0 x (2^1) + 0 x (2^0) which becomes 16 + 0 + 4 + 0 + 0 = 20.

Bada bing, bada boom! We've written 20 in binary code and converted binary code to decimal numbers!

Now it's time to write 25 in binary code.

Step 1: Result 12; remainder 1.
Step 2: Result 6; remainder 0.
Step 3: Result 3; remainder 0.
Step 4: Result 1; remainder 1.
Step 5: 1 divided by 2; no can do! Result 0; remainder 1.

Reversing our sequence, we get:

Step 5: 1
Step 4: 1
Step 3: 0
Step 2: 0
Step 1: 1

25 in binary code is therefore 1 1 0 0 1.

Time to plug and chug to check our math.....

1 x (2^4) + 1 x (2^3) + 0 x (2^2) + 0 x (2^1) + 1 x (2^0) which becomes 16 + 8 + 0 + 0 + 1 = 25.

Now here's where the bitwise AND part comes into play. Let's examine our binary representations of 20 and 25 again.....

20: 1 0 1 0 0
25: 1 1 0 0 1

The bitwise AND operator looks at the binary strings being combined to see whether they've got 0's or 1's at a given position. The basic gist of bitwise AND is that.....

1 and 1 make 1
0 and 1 make 0
0 and 0 make 0 for a given position in a binary string.


Proceeding from left to right, we get: 1 0 0 0 0 which becomes.....

1 x (2^4) + 0 x (2^3) + 0 x (2^2) + 0 x (2^1) + 0 x (2^0) or 16 + 0 + 0 + 0 + 0 = 16.

As we can see, bitwise AND works in wacky ways! If we combine 20 and 25 in the decimal system, we of course get 45. But if we combine the binary representations of 20 and 25 in bitwise AND, we end up with a string that equals 16! [huh]

Anyhow, I'm sorry if this post was too long-winded and I hope this helps anybody who might be having trouble with the bitwise AND operator.


Profile

Posted on: Mon Jun 04, 2018 6:39 pm




Posts: 931
Location: Ladysmith, BC, Canada
Joined: Fri May 13, 2011 1:37 am
Post Re: Bitwise AND
Skeeter84: Thank you for trying to get some understanding of this concept to me as well as other users...I do appreciate the time it took you to write out the explanation.........I hope others DO get something from your explanation.......I can follow the logic for the explanation but I get "lost" when trying to figure out another number..........I think " this old dog of 73 cannot learn new tricks".........I will have to skip such puzzles in the future and stick with what I know ( which is not much) when compared to users like yourself.......beaker


Profile

Posted on: Mon Jun 04, 2018 11:36 pm




Posts: 691
Joined: Wed Apr 16, 2014 9:20 pm
Post Re: Bitwise AND
Beaker,

I learned binary at a young age and have had to use it throughout my life.

I know my powers of 2: - represented in binary (base 2)
1 = 2^0 - 0000 0001
2 = 2^1 - 0000 0010
4 = 2^2 - 0000 0100
8 = 2^3 - 0000 1000
16 = 2^4 - 0001 0000
32 = 2^5 - 0010 0000
64 = 2^6 - 0100 0000
128 = 2^7 - 1000 0000

Given the size of the puzzles I do not why you would need to go further.

Rather than rafael's algorithm, I look for the largest power of 2 in a given number, say 73 (or 15)

73 - largest power of 2 is 64. Write down a 1 for 2^6 -- 1?
73 - 64 = 9. 9 is smaller than 32, and 16. Write down to the two zeros for 2^5, and 2^4 to the right of the original 1 --100?
9 - 8 = 1. Write down a 1 for 2^3 -- 1001?
1 is smaller than 4 and 2. Write down two zeros for 2^2, and 2^1 --100100?
1 is left. The number is odd 1 = 2^0. Write down a final 1

Final answer 73 = 1001001 (base 2)

15 --
The largest power of 2 that fits into 15 is 8 (2^3) - write down a 1 for 2^3 -- 1?
15 - 8 = 7
The largest power of 2 that fits into 7 is 4 (2^2) - write down a 1 for 2^2 -- 11?
7- 4 = 3
The largest power of 2 that fits into 3 is 2 (2^1) - write down a 1 for 2^1 --111?
3 - 2 = 1
1 is left. The number is odd. Write down a final 1.

15 = 1111 (base 2)

Now lets do an even number, 28
The largest pwer of 2 that fits into 28 is 16 = 2^4. Write down a 1 -- 1?
28 - 16 = 12
The largest power of 2 that fits into 12 is 8 = 2^3. Write down a 1 -- 11?
12 - 8 = 4
The largest power of 3 that fits into 4 is 4 2^2. Write down a 1 -- 111?
There is no 2 left over, we need a place holer for 2^1. Write down a zero -- 1110?
There is no 1, we need a place holder for 2^0. Write down a zero -- 11100

28 = 11100 (base 2)

I do not know if this method is easier or not. Its just the way I think about it.


Profile

Posted on: Tue Sep 29, 2020 4:58 pm




Posts: 9
Joined: Sat Mar 10, 2012 7:50 pm
Post Re: Bitwise AND
What can we assume about the binary representation of negative numbers, e.g. book puzzle a4v16 ?


Profile
Display posts from previous:  Sort by  
Reply to topic   [ 11 posts ]  Go to page 1, 2  Next

You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
cron
All forum contents © Patrick Min, and by the post authors.

Forum software phpBB © 2000, 2002, 2005, 2007 phpBB Group.
Designed by STSoftware.