StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

PO
primarykey
Id
1693208
data
AcceptedAnswerId
0
AnswerCount
0
ClosedDate
CommentCount
2
CommunityOwnedDate
CreationDate
2009-11-07T14:27:38.657
FavoriteCount
0
LastActivityDate
2009-11-07T14:27:38.657
LastEditDate
LastEditorUserId
0
OwnerUserId
57461
ParentId
1692802
PostTypeId
2
Score
5
ViewCount
0
LastEditorDisplayName
text
Body
<blockquote> In this case, I can see that it works, but I am not sure what the logic is? And I am not sure I can create my own bit operations like this from scratch. How do I start thinking in bits? </blockquote> People have answered your first question -- explaining the logic. I shall hopefully show you a terribly basic, long-winded but standard method of making any bit twiddling operations. (note, once you get used to working with bits you'll start thinking in & and | straight off without doing such nonsense). <ol> <li>Figure out what you'd like your operation to do.</li> <li>Write out a FULL truth table. </li> <li>Either read the sum-of-products direct from the table or make a Karnaugh map. The km will reduce the final eqution a lot.</li> <li>???</li> <li>Profit</li> </ol> Deriving for the example you gave. ie, where a mask selects bits from A or B. (0 is A, 1 is B) This table is for 1 bit per input. I'm not doing more than one bit, as I don't want to waste my time :) ( why? 2^(2bits * 3inputs) = 64 cases :( 2^(3bits * 3inputs) = 512 cases :(() But the good news is that in this case the operation is independant of the number of bits, so a 1 bit example is 100% fine. Infact it's recommended by me :) <pre><code>| A | B | M || R | ============++==== | 0 | 0 | 0 || 0 | | 0 | 0 | 1 || 0 | | 0 | 1 | 0 || 0 | | 0 | 1 | 1 || 1 | | 1 | 0 | 0 || 1 | | 1 | 0 | 1 || 0 | | 1 | 1 | 0 || 1 | | 1 | 1 | 1 || 1 | </code></pre> Hopefully you can see how this truth table works. how to get an expression from this? Two methods: KMaps and by-hand. Let's do it by-hand first, should we? :) Looking at the points where R is true, we see: <pre><code>| A | B | M || R | ============++==== | 0 | 1 | 1 || 1 | | 1 | 0 | 0 || 1 | | 1 | 1 | 0 || 1 | | 1 | 1 | 1 || 1 | </code></pre> From this we can dervive an expresion: <pre><code>R = (~A & B & M) | ( A & ~B & ~M) | ( A & B & ~M) | ( A & B & M) | </code></pre> Hopefully you can see how this works: just or together the full expressions seen in each case. By full I imply that you need to not-variables i nthere. Let's try it in python: <pre><code>a = 0xAE #10101110b b = 0x64 #01100011b m = 0xF0 #11110000b r = (~a & b & m) | ( a & ~b & ~m) | ( a & b & ~m) | ( a & b & m) print hex(r) </code></pre> OUTPUT: <pre><code>0x6E </code></pre> These numbers are from Abel's example. The output is <code>0x6E</code>, which is <code>01101110b</code>. So it worked! Hurrah. (ps, it's possible to derive an expression for ~r from the first table, should you wish to do so. Just take the cases where r is 0). This expression you've made is a boolean "sum of products", aka Disjunctive Normal Form, although DNF is really the term used when using first-order predicate logic. This expression is also pretty unweidly. Making it smaller is a tedious thing to do on paper, and is the kind of thing you'll do 500,000 times at Uni' on a CS degree if you take the compiler or hardware courses. (Highly recommended :)) So let's do some boolean algebra magic on this (don't try and follow this, it's a waste of time): <pre><code>(~a & b & m) | ( a & ~b & ~m) | ( a & b & ~m) | ( a & b & m) |= ((~a & b & m) | ( a & ~b & ~m)) | ( a & b & ~m) | ( a & b & m) </code></pre> take that first sub-clause that I made: <pre><code>((~a & b & m) | ( a & ~b & ~m)) |= (~a | (a & ~b & ~m)) & (b | ( a & ~b & ~m)) & (m | ( a & ~b & ~m)) |= ((~a | a) & (a | ~b) &( a | ~m)) & (b | ( a & ~b & ~m)) & (m | ( a & ~b & ~m)) |= (T & (a | ~b) &( a | ~m)) & (b | ( a & ~b & ~m)) & (m | ( a & ~b & ~m)) |= ((a | ~b) & (a | ~m)) & (b | ( a & ~b & ~m)) & (m | ( a & ~b & ~m)) </code></pre> etc etc etc. This is the massively tedious bit incase you didn't guess. So just whack the expression in a website of your <a href="http://hopper.unco.edu/KARNAUGH/Function.html" rel="nofollow noreferrer">choice</a>, which will tell you <pre><code>r = (a & ~m) | (b & m) </code></pre> Hurrah! Correct result. Note, it might even go so far as giving you an expression involving XORs, but who cares? Actually, some people do, as the expression with <code>and</code>s and <code>or</code>s is 4 operations (1 <code>or</code>, 2 <code>and</code>, 1 <code>neg</code>), whilst <code>r = a ^ ((a ^ b) & mask)</code> is 3 (2 <code>xor</code>, 1 <code>and</code>). Now, how do you do it with kmaps? Well, first you need to know how to make them, I'll leave you to do that. :) Just google for it. There's software available, but I think it's best to do it by hand -- it's more fun and the programs don't allow you to cheat. Cheat? Well, if you have lots of inputs, it's often best to reduce the table like so: <pre><code>| A | B | M || R | ============++==== | X | X | 0 || A | | X | X | 1 || B | </code></pre> eg that 64 case table? <pre><code>| A1| A0| B1| B0| M1| M0|| R1| R0| ========================++======== | X | X | X | X | 0 | 0 || A1| A0| | X | X | X | X | 0 | 1 || A1| B0| | X | X | X | X | 1 | 0 || B1| A0| | X | X | X | X | 1 | 1 || B1| B0| </code></pre> Boils down to 4 cases in this example :) (Where X is "don't care".) Then put that table in your Kmap. Once again, an exercise for you to work out [ie, I've forgotten how to do this]. Hopefully you can now derive your own boolean madness, given a set of inputs and an expected set of outputs. Have fun.
Tags
Title
singulars
PostAcceptedAnswerId
1. This table or related slice is empty.
PostParentId
1. POHow to think of bit operations for simple operations?
 singulars
 PostTypePostTypeId
 PTQuestion
PostTypePostTypeId
1. PTAnswer
UserLastEditorUserId
1. This table or related slice is empty.
UserOwnerUserId
1. USPod
plurals
PostLinksPostIdRelatedPostId
1. This table or related slice is empty.
PostLinksRelatedPostIdPostId
1. This table or related slice is empty.
PostsAcceptedAnswerId
1. POHow to think of bit operations for simple operations?
 singulars
 PostTypePostTypeId
 PTQuestion
PostsParentIdCreationDate
1. This table or related slice is empty.
VotesPostIdCreationDate
1. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
2. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
3. VO
 singulars
 PostPostId
 PO
 UserUserId
 This table or related slice is empty.
 VoteTypeVoteTypeId
 VTUpMod
CommentsPostId
1. CO+1 Interesting and thorough, nice fast-paced tutorial
 singulars
 PostPostId
 PO
 UserUserId
 USAbel
2. CO+1 for K-maps. Once you get used to them, they're super-handy for smaller binary truth tables.
 singulars
 PostPostId
 PO
 UserUserId
 USTim

Querying!

Guidance

A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.