[pdpi]

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

[beaumayns]

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

[coinomega]

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

C

[wyldfire]

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.

[pdpi]

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.

[jonsen]

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

[saynsedit]

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

[pdpi]

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

[saynsedit]

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?

[pdpi]

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.

[saynsedit]

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.

[jonsen]

I think it works, if you do it right:

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

[hkjgkjy]

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

[homegarlic]

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

[forgotpwtomain]

> - convert x and y from decimal to binary

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

[pdpi]

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

[forgotpwtomain]

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

[pdpi]

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.

[forgotpwtomain]

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?

[jonsen]

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