7 ms·
The beauty of bitwise AND
- dingo_bat 10y agoI always thought ^ is the XOR operator, not AND.
- posterboy 10y agoIn boolean algebra, * (a dot, actually) and + are used for And and Or and the usual rules about association and commutation are used (PEMDAS, kinda, ommiting the * on occasion). Sometimes, what I might call, up arrow and down arrow are used, looking similar to ^ and v, in relation to set arithmetic symbols for the union and intersection oprators.
- svalorzen 10y agoAnother way to easily remember the arrows is to associate them with words: ^ with the A of and, and v with the V for vel (Latin for or). I always did this in logic class since I would always get confused otherwise.
- dnautics 10y agoAlso useful is making the arrows round-ended makes the the union/intersection signs, with or being union and and bring intersection (as it would be with the corresponding indicator functions).
- TeMPOraL 10y agoI remembered these and union/intersection sign by imagining balls falling on the symbols from above - in case of V (OR) they would end up inside the symbol, which suggest summing/union, and in case of ^ (AND) they would get split and collect on opposite sides.
- kkaja 10y agoThe post is using boolean algebra symbols.
- Tomte 10y agoYes, it is. But ^ and ∧ are different.
- turbohedgehog 10y ago⊕ would be XOR using mathematical notation
- coinomega 10y agoI used the notations found in FIPS 180-4 http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf
- lokedhs 10y agoCan someone explain this sentence to me? (In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?) f(a, b) produces at most a or b, whichever is greater: f(a, b) ≤ max(a, b) As far as I can tell, the result can never be greater than the smaller of a and b. I can't come up with a counterexample. Is there one?
- eximius 10y agoI think you're right. By definition it can't have any more 1's that the lesser has and it might have less 1's than the lesser has.
- nthacker 10y agoYeah for an AND function, f(a,b) <= min(a,b)
- deleted 10y ago[deleted]
- Gankro 10y agoYou're correct, it can be changed to `min(a, b)`. A rough proof: * assume WLOG `a = min(a, b)` * `a & b` takes the set bits of `a` and produces a subset of them * the value of an integer is `SUM 2^j` where the j-th bit is set * removing positive elements from a sum can only make it smaller * therefore & can only produce a value smaller than `a` (the minimum)
- deleted 10y ago[deleted]
- Strilanc 10y agoA counterexample is 0 & -1 == 0.
- thedufer 10y agoThe given function is clearly only defined over naturals. In the first part using bits, there's no indication of how to encode negatives, and in the second part with the sum equation, f(-1,-1) >= 0 (and thus not equal to -1) for any reasonable definition of the modulo function paired with any `b`, which breaks one of the stated identities. In fact, that's true if you replace mod with _any_ function.
- bugmenot3 10y agoI knew I'd seen this pattern before! The XOR texture [1] is very similar. Apparently it was overused in early 2D games to test texture mappers (or for "fancy floor tiles", lol) Actually, looking at the XOR, AND, OR textures side by side, it's easy to gain more intuition for them. I definitely recommend reading some of the articles at [2], they're pretty entertaining and straight-forward. [1] http://lodev.org/cgtutor/xortexture.html http://lodev.org/cgtutor/xortexture.html [2] http://lodev.org/cgtutor/ http://lodev.org/cgtutor/
- chriswarbo 10y agoFrom the first link: > But who'd want to generate a 1024x1024 XOR texture anyway. The article contains a 1024x1024 AND texture :)
- UlyssesSKrunk 10y agoDamn dude, that site is addicting. Like buzzfeed but for the overlap of math and CS nerds.
- userbinator 10y agoVery common in the demoscene too, along with the related Sierpinski triangle texture: https://en.wikipedia.org/wiki/File:Multigrade_operator_AND.svg https://en.wikipedia.org/wiki/File:Multigrade_operator_AND.s...
- known 10y agoXOR swap algorithm https://en.wikipedia.org/wiki/XOR_swap_algorithm https://en.wikipedia.org/wiki/XOR_swap_algorithm
- tr352 10y agoThe complexity of the formula and the "striking features" of the graph only demonstrate that operations defined in one base (AND is nothing but multiplication in base 2) may behave in complex and non obvious ways in other bases.
- TTPrograms 10y agoAND is vector entry-wise multiplication (hadamard product) with boolean entries, not just multiplication in base 2. Multiplication between numbers is not affected by base - base just defines how the number is written down.
- chriswarbo 10y ago> The complexity of the formula and the "striking features" of the graph only demonstrate that operations defined in one base (AND is nothing but multiplication in base 2) may behave in complex and non obvious ways in other bases. I'd go a little further: the complexity of the formula only demonstrates that trying to fit a square peg (bitwise boolean algebra) into a round hole (numeric algebra) can cause things to get complicated. In particular, the author seems to think that "math" means "numbers": > the AND function is in fact mathematically non-trivial: > The mathematical equivalent of AND > Now, if you find that function dreadful — I am with you. When I first wrote it down, I found it both complicated and unhelpful; after formulating it, my mind was no closer to understanding the kind of pattern the AND function followed, if any. > Ignoring the complex math formula above, we can still find a number of interesting properties regarding the AND function. This implies that bitwise boolean algebra is somehow 'not math', and the complex formula somehow 'is math'. In fact math can deal with anything that's precisely defined, and includes fields like geometry, topology, logic, category theory, universal algebra, set theory, type theory, etc. which aren't particularly related to numbers. Whilst we could represent, say, logic, using a numerical formula (e.g. based on Goedel numbers) it's usually the wrong thing to do ;) I think this may be a side-effect of the poor state of math education; i.e. we're taught to perform numerical calculations and not much else. :(
- snaky 10y agoThe beauty of shift - http://yarchive.net/comp/shift_instruction.html http://yarchive.net/comp/shift_instruction.html
- e19293001 10y agoI remember I asked a question 5 years ago in stack overflow[0] about the mathematical equation equivalent of bitwise AND. Thank you for posting this I found the answer to my 5 year old question. [0] - http://stackoverflow.com/questions/7199625/mathematical-equation-for-and-bitwise-operation http://stackoverflow.com/questions/7199625/mathematical-equa...
- jonsen 10y agoThe formula in the accepted answer on SO is equivalent to the formula in this article. Just written differently.
- atemerev 10y agoI remember the pattern, I do! Back in the year 1992, when I was 9 years old, I participated in the first tour of Russian programming olympiad. The first challenge was this one: "On the infinite coordinate grid (positive integers only), start with the number 0 in the cell with coordinates (0,0). Then, in each cell in the neighbourhood, write the largest integer that hadn't yet appeared in the same row or column. Repeat indefinitely. Find the formula for obtaining the value inside any arbitrary cell in the grid." I have filled a 16x16 grid using this definition manually (of course, the programming olympiad had nothing to do with computers — similar to whiteboard coding during the job interviews these days), and obtained similar pattern. As this task was by far the most interesting in the problem set, I have spent the entire allotted time trying to figure out the formula, without success — so I got 0 points and went out of the competition. And now, 24 years later, I see the solution (not the AND; the pattern looks slightly different, perhaps XOR?) But I should have tried bitwise operations back then. Damn it!
- deleted 10y ago[deleted]
- Sniffnoy 10y agoDo you mean the smallest whole number that hasn't appeared yet? But yup, that's a well-known recursion for XOR, important in combinatorial game theory, in which context it's often known as the Nim sum. (Note by the way, that the initial condition about (0,0) can be omitted -- at that point, there are no numbers in that row or column, so the smallest one available is 0!) Topics you might want to look up: https://en.wikipedia.org/wiki/Combinatorial_game_theory https://en.wikipedia.org/wiki/Combinatorial_game_theory https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Nim https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem https://en.wikipedia.org/wiki/Mex_(mathematics) https://en.wikipedia.org/wiki/Mex_(mathematics) https://en.wikipedia.org/wiki/Nimber https://en.wikipedia.org/wiki/Nimber
- atemerev 10y agoYes, the smallest, of course.
- inductiveload 10y agoEvery binary operation has an associated texture. If you plot integer operations as colours or rings[1], you get other interesting results that provide insights into how the operands affect the result. [1] https://commons.wikimedia.org/wiki/Category:Binary_ring_diagrams https://commons.wikimedia.org/wiki/Category:Binary_ring_diag...
- pdpi 10y ago"Bitwise" is really shorthand for "this is an operation that acts on the representation of a number in base-2, rather than on the number itself", so it's no surprise that it doesn't translate well to base 10. The reason why that formula is so gnarly is that it does three things in one go: - convert x and y from decimal to binary - calculate x AND y at each digit (by using the property that x AND y is isomorphic to multiplication mod 2) - convert back to decimal. Instead of trying to understand bitwise AND in this way, we could try building the equivalent operation in base 10, and see where that leads us. One simple way of achieving this is by simply saying that x AND Y is digit-wise MIN, and x OR y is digit-wise MAX. Note how, under that interpretation, this works in both binary and decimal (or hex, or octal, or whatever other base you want: 101 AND 110 = 100 101 OR 110 = 111 Or using digits not available in binary: 124 AND 310 = 110 124 OR 310 = 324 Again, this works independently of whether you're using octal, decimal, hex, or something else >= 5.
- hkjgkjy 10y agoThis is very clever - thank you for sharing. I will remember this.
- homegarlic 10y agoThis is a common approach in fuzzy logic. They are called there Zadeh OR and Zadeh AND - by the mathematician https://en.wikipedia.org/wiki/Lotfi_A._Zadeh https://en.wikipedia.org/wiki/Lotfi_A._Zadeh
- saynsedit 10y agoDid you just make this up? Is the digit-wise MIN abstraction of bitwise AND more widely applicable?
- pdpi 10y agoTo be honest? Yes, I did make it up on the spot, because my reaction to the post was "there has to be a better way to interpret bitwise AND operating on decimals". What I cared about was that we could build some sort of extension for bitwise AND that operated on any base in a completely consistent way, with no considerations for whether that interpretation is in widespread use. I must confess to being quite chuffed that homegarlic has since commented that this is consistent with how Zadeh fuzzy set theory works (though that uses reals in the [0,1] range rather than modular arithmetic).
- threepipeproblm 10y agoIf b is the number of bits, shouldn't the upper bound of the sigma be b-1?
- coinomega 10y agocorrected
- joveian 10y agoI like the 1024x1024 picture; it looks a bit like a bird to me, or maybe a stingray. One interesting application of bitwise AND is in cryptography, particularly LRX (logical rotations and xor) algorithms popularized by Keccak/SHA-3. By using only these limited operations, masking (blinding) becomes much more efficient that makes various side channel attacks harder [0]. Several of the CAESAR AEAD competition candidates are LRX. NORX uses only AND, XOR, and rotation. [0] http://keccak.noekeon.org/NoteSideChannelAttacks.pdf http://keccak.noekeon.org/NoteSideChannelAttacks.pdf
- _RPM 10y agoThe image seems to be doing b1 ^ b2 (which would be a XOR), but the result is the result of & (AND)