The beauty of bitwise AND | Hacker News Reader

The beauty of bitwise AND

medium.com

161 pointscoinomega83 comments

"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.

This is very clever - thank you for sharing. I will remember this.

This 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

Did you just make this up? Is the digit-wise MIN abstraction of bitwise AND more widely applicable?

To 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).

With all due respect, digit-wise MIN seems like an unnecessary abstraction in same vein as AbstractManagerFactoryFactory.

If the abstraction doesn't have generally applicable higher-level properties, it's probably not worth abstracting.

After all, bit-wise AND is only one of 16 possible two-argument bit functions. Shall we create a digit analog for all 16 of them?

As other people have said in this thread, the interpretation of AND and OR as MIN and MAX respectively _is_ a useful one, and it sees applications in fuzzy logic.

Given that, looking at decimal digit-wise AND under that lens isn't about introducing a new abstraction, it's about applying an existing abstraction to a new domain.

One litmus test to check the usefulness of an abstraction is to see if it conforms to existing laws of the specific case.

Let's use distributivity of AND over OR:

    a & (b | c) = a & b | a & c

This also works in the abstraction of Boolean algebra to normal algebra:

    a * (b + c) = a * b + a * c

What about with your digit MIN/MAX abstraction:

    MIN(a,MAX(b,c)) = MIN(MAX(a,b),MAX(a,c))

Well... No, this does not generally hold. If b and c are both larger than a, then this equality fails.

Distributivity is a pretty important property. Without it, your MIN/MAX algebra just has commutivity and associativity which arguably aren't very unique considering all other possible commutive/associative functions. In any case, losing a property dramatically decreases the usefulness of your algebraic abstraction.

Another wart in your abstraction is the missing NOT operation, further deteriorating its usefulness.

Just because the MIN abstraction works for the AND case, that's not enough to make it a worthwhile abstraction. What happens when you want to do more complex yet natural operations like a & (b | c)? In the same vein, AbstractManagerFactoryFactory may seem elegant now, but it may make it harder for new code to do trivial things down the road.

I think it works, if you do it right:

  MIN(a,MAX(b,c)) = MAX(MIN(a,b),MIN(a,c))

It does, I stand corrected.

And so does

  MAX(a,MIN(b,c)) = MIN(MAX(a,b),MAX(a,c))

so it is even more useful than normal algebra :p

Fuzzy logic has insane amounts of similar ORs and ANDs that also have to conform some simple laws.

Generalization of ANDs and ORs is called t-norms and t-conorms (s-norms). They have to satisfy laws of monotonicity, commutativity and associativity.

So all kinds of magical ANDs and ORs spawn to meet the requirements.

I'm not really a fan of fuzzy logic but it really is a nice exercise in mathematics.

This is in fact the approach taken in the k language:

http://code.kx.com/wiki/Reference/Bar http://code.kx.com/wiki/Reference/Ampersand

This is pretty interesting, but I'm missing something. Intuitively, your digit-wise MIN description of 'AND' makes sense to me. But your examples don't work when using two's complement encoded versions of them. 124 & 310 == 52 right? Help me connect the dots.

Right. Two's complement is binary. Think decimal hardware (which might use ten's complement for negative numbers).

See it this way: Numbers are distinct from their representations. 0x10, 0o20, 16 and 0b10000 are four different representations of the same number. The & operator doesn't operate on _numbers_, it operates on their binary representation — in many ways, it's almost like string manipulation.

What I suggested was that that way of operating on the representation of the number would work on any base in a way that is consistent (but, importantly, doesn't yield the same numerical result!) with the binary version.

> - convert x and y from decimal to binary

What?! What exactly is at the memory address that you think it's converting?

I'm talking specifically about this formula[1] rather than what's happening at the hardware level!

1 - https://d262ilb51hltx0.cloudfront.net/max/800/1*Y5WC--jvMMdU...

But that's only happening in your head. It's an implementation detail of your shell/ide that you are reading numbers in base10.

From the post: "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."

That's what I'm railing against. If your objective is to understand how bitwise-AND works, trying to decipher it directly in base-10 is folly. I'm not a fan of the graphical approach taken by the post either, and prefer the algebraic way out, which is why I proposed an algebraic base-10 (any-base, really) version.

But your algebraic arithmetic with max-wise and min-wise characters is not equivalent at all! In fact it's a terrible analogy.

Bit-wise arithmetic is great because it's operations are compatible with propositional calculus,- but I cannot see how you can do anything productive with min/max-wise defined AND/OR for base10. For example how to do you determine 324 XOR 310 in your notation?

In this decimal digit context it would be appropriate to define

  NOT d = 9 - d

Similar to

  NOT b = 1 - b

for binary digits. And in fuzzy logic.

Taking the logic identity

  a XOR b = ( a AND NOT b ) OR ( NOT a AND b )

it would be

  MAX( MIN( a, NOT( b ) ), MIN( NOT( a ), b ) )

> "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"

I would argue that while bitwise operations are indeed more easily represented/computed in base 2 than in base 10, they do act on the 'number itself', whichever base you then represent this number in. ... at least in the approach I took, where I treat bit strings as representations of 'numbers', specifically positive integers. If you think of such operations as manipulating 'strings' of characters - whatever character set those are taken from - rather than numbers then indeed we indeed arrive to different conclusions, and your digit-wise MIN generalization makes sense.

I think both approaches are meaningful, although conceptually different, and I have tried, however clumsily, to explain the 2 approaches in a previous post (https://medium.com/biffures/bits-101-120f75aeb75a#.fc93no6od) before settling for the 'number' approach for this post.

I am actually not a proponent of using base 10 as the standard view for bitwise operations, I merely use that base to show that the function looks complicated in base 10 and brings little further intuition on what pattern AND follows. Note that the rest of the article and all visualizations are NOT base-dependent and do not use the base-10 formula. (I did write my numbers in base-10 in the sketches simply out of convenience, but feel free to translate to any base).

Is this revolutionary? Certainly not. But I do think the graphs look cool, and I was happy to share them. Hope this clarifies some of the thinking behind the post; and thanks for the constructive thoughts! - seems like I can do plenty of read-up .-)

I 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

[2] http://lodev.org/cgtutor/

From the first link:

> But who'd want to generate a 1024x1024 XOR texture anyway.

The article contains a 1024x1024 AND texture :)

Damn dude, that site is addicting. Like buzzfeed but for the overlap of math and CS nerds.

Very common in the demoscene too, along with the related Sierpinski triangle texture:

https://en.wikipedia.org/wiki/File:Multigrade_operator_AND.s...

I 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!

Do 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/Nim https://en.wikipedia.org/wiki/Sprague%E2%80%93Grundy_theorem https://en.wikipedia.org/wiki/Mex_(mathematics) https://en.wikipedia.org/wiki/Nimber

Yes, the smallest, of course.

Can 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?

I 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.

Yeah for an AND function, f(a,b) <= min(a,b)

You'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)

A counterexample is 0 & -1 == 0.

The 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.

> The given function is clearly only defined over naturals.

The post doesn't specify. Programming languages do define it over the negatives, however. I just didn't want anyone going into python and asserting that a & b >= min(a,b).

> there's no indication of how to encode negatives

Just do the standard thing: use 2s complement arithmetic [1]. More concretely: set b to infinity and take the limit under the 2-adic metric [2]. For example, -2 & -1 has partial sums 0, 10, 110, 1110, 11110, etc. It's limiting to ...1111110, which is the 2's complement representation of -2.

1: https://en.wikipedia.org/wiki/Two%27s_complement

2: https://en.wikipedia.org/wiki/P-adic_number

I'm not quite sure they have enough paper for numbers with infinite boolean expansions.

The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?

Pick any `b` you want, even infinity, and evaluate:

    sum_n^b 2^n (floor(0/2^n) mod 2) (floor(-1/2^n) mod 2)

    sum_n^b 2^n * 0 * 1

    sum_n^b 0

    0

Excellent. I'm glad we agree. You'll notice that the stated identity f(x,x) = x fails to hold over x < 0. I hope this is sufficient to make it clear that the equation does not consider the negatives?

Seems to work fine for -1:

    f(-1, -1)
    = sum_{n=0}^b 2^n (floor(-1/2^n) mod 2) (floor(-1/2^n) mod 2)
    = sum_{n=0}^b 2^n * 1 * 1
    = 1 + 10 + 100 + 1000 + ... [in binary]
    = ...11111 [in the 2-adics]
    = -1

There is not, and there cannot be. However, even if he was figuring this all out from scratch, he could not have come up with the hand-written charts without realizing that.

I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance.

However, I cannot present to you the crucial difference between the maximum of two numbers and the minimum of two numbers that explains what he was thinking. This must exist for my hypothesized explanation to make sense.

> I'm going to go out on a limb and guess that it is of some habitual relevance to a mathematician, since he mentions the identity function (not really relevant here either), but that the material he actually explains here doesn't do anything to justify its appearance.

It's worse than that; he mentions the identity function only to make a gross error about it. The identity function on (a, a) is (a, a), not a.

I don't think you need to be so unforgiving?

If you want extra precision, a -> f(a, a) is Id.

Knowing that helped me understand one property of the chart, never said that was the most stunning of properties, and the best articulated one :-)

> If you want extra precision, a -> f(a, a) is Id.

What does this mean?

The function which to any integer a associates f(a, a) with f defined as in the article is the identity function on the natural integer set.

Granted. g(a) = f(a,a) is indeed the identity function for all f such that f(a,a) = a. That seems pretty pointless as an observation. We have f, so we're observing that some other, unrelated function is the identity function?

Assuming you actually care about the answer, this just help me drew the exploratory graph, and this property was useful to fill in cells for which operands were equal. Finding obvious properties is a great way to learn a pattern without even computing things. Unlike what you may think, I had no idea what I was about to find - I had never seen this chart drawn before, and so this post is structured around how I thought about the exploration, not around how it may be presented to an audience who already knows way more than I do on bitwise operations. Sounds fair?

Sure it's fair. Bitwise operations produce pretty strange numeric results, so no, I wouldn't think you'd expect much going in. But I don't see where the identity function comes into it at all. It looks like the term "the identity function" stuck in your mind, and you reached for it when you found something subjectively similar. But shared semantic space isn't a good reason to say that a function which isn't the identity function, is. Your middle point is the observation "f(a,a) = a", which is perfectly valid, but is not the same finding as the finding you report. Using pretty-simple terms to state something true is generally preferable to using even simpler terms to state something false.

It is fair enough, that you find the law f(a,a) = a useful. Just don't call it the identity function when it is not.

The law x AND 1 = x is called the identity law.

The law x AND x = x is called the idempotence law.

Nothing to do with the identity function.

> In the quote below, he names the AND function "f", which in itself is a bit strange. What's wrong with "and" or ∧?

'∧' usually denotes the logical AND operator, which does not operate on integer values, (i.e. writing 22 ∧ 78 = 6 is weird). So it's not a bad idea to give this function a different name.

He could have made that explicit though.

Every 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_diag...

I always thought ^ is the XOR operator, not AND.

In 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.

Another 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.

Also 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).

I 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.

The post is using boolean algebra symbols.

Yes, it is.

But ^ and ∧ are different.

⊕ would be XOR using mathematical notation

I used the notations found in FIPS 180-4 http://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.180-4.pdf

I 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

The beauty of shift - http://yarchive.net/comp/shift_instruction.html

I 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-equa...

The formula in the accepted answer on SO is equivalent to the formula in this article. Just written differently.

If b is the number of bits, shouldn't the upper bound of the sigma be b-1?

corrected

The image seems to be doing b1 ^ b2 (which would be a XOR), but the result is the result of & (AND)

∧ is also the notation for bitwise AND

http://csrc.nist.gov/publications/fips/fips180-4/fips-180-4....

Ahh. Okay. I'm just assuming that they would do these computations using a C like language.

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.

AND 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.

It's multiplication in the sense that for two base-2 numbers A and B, A & B is the same as A * B, but I get your point.

For two bits AND is multiply, not for two numbers in general, regardless of base.

> 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. :(

Hello Chris, author here!

AND is not multiplication in base 2 :)

The point of the article was to make sense of the apparent complicatedness of the math formula through nice visuals that help humans understand what AND does number-wise.

I may have used the terms math vs. numbers loosely, but this seemed to be the terms most people would understand - and a vocabulary used in other places (Wikipedia, though maybe hardly a reference?). I have tried to explain my "bit string" vs "number" approach [in this other article](https://medium.com/biffures/bits-101-120f75aeb75a#.gz4ka3t7k) if you are interested.

Really not implying that boolean algebra is not math though - and I am pretty sure this has nothing to do with the 'poor state of math education'.

I still think the approach is kind of misleading. Because the (apparent) complexity of the math formula is only linked to the fact you're using a decimal formula for a binary operation.

The operation, mathematically, is extremely simple.

Fair, changed paragraph to "While the result is easily computed and the process easily understood in base 2 (i.e., using the ‘bit strings as language’ lens), the AND function written in base-10 notation looks in fact non-trivial:"

The point of the article is to switch bases (exploring the many facets).

Per my previous thoughts, "the binary notation is a contingency, useful to understand and define specific functions that will run fast on computers given their binary architectures. However, because the notation does not convey meaning in itself, those numbers and functions are as well described in any arbitrary base, namely base 10 for humans, or base 16 (hexadecimal) for conciseness."

> The operation, mathematically, is extremely simple.

You're absolutely right, and this was my main problem; labelling the complicated version as 'math' seems to imply that the simple definitions, the wonderful patterns, etc. are somehow 'not math'.

> a decimal formula for a binary operation

It's not the base which makes it complicated; it's extracting each digit individually. Using the same approach to define a digit-wise operation in base 10 would be just as nasty, except you'd have powers of 10 instead of powers of 2, and mod 10 instead of mod 2.

In other words, just because decimal lets you write numbers like "946", it doesn't make it trivial to get the "9", "4" or "6" individually using 'highschool algebra'; you need to use mod, division, floor/subtraction, powers of ten, etc. just like that formula does for base 2.

Of course, if we don't stick to highschool algebra, it can be as trivial as we like. "The digits of 946" is a perfectly well defined mathematical/numerical operation, so we can just say that and we're done. Likewise, we can make a trivial formula for bitwise AND, like "x ^ y", by defining "^" as 'bitwise AND'.

In a way, formulas like that given in the article are only complicated because they're making assumptions about some operations being 'more fundamental' than others; but in "real" math (i.e. not highschool rote learning and number crunching), we're free to use whatever operations we want, as long as we define them precisely; "bitwise AND" is a perfectly fine definition, and just as good as "addition" or "multiplication".

You're perfectly welcome to define operators in terms of other things you consider to be 'more fundamental'; Russell and Whitehead famously did this in Principia Mathematica, considering sets to be more fundamental than arithmetic and requiring 300+ pages to reach a proof of "1 + 1 = 2".

Yet Goedel showed that no set of axioms is 'best', in which case you might as well use whichever ones make life easiest. When you're calling a formula "dreadful", it implies that you've not made your life easy ;)

Yes, but and is multiplication in Z2

XOR swap algorithm https://en.wikipedia.org/wiki/XOR_swap_algorithm

Reply on news.ycombinator.com