5 ms·
"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 sur
by 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.
- 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).
- saynsedit 10y agoWith 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 10y agoAs 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.
- deleted 10y ago[deleted]
- saynsedit 10y agoOne 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.
- deleted 10y ago[deleted]
- 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
- beaumayns 10y agoThis is in fact the approach taken in the k language: http://code.kx.com/wiki/Reference/Bar http://code.kx.com/wiki/Reference/Bar http://code.kx.com/wiki/Reference/Ampersand http://code.kx.com/wiki/Reference/Ampersand
- wyldfire 10y agoThis 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.
- jonsen 10y agoRight. Two's complement is binary. Think decimal hardware (which might use ten's complement for negative numbers).
- pdpi 10y agoSee 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.
- forgotpwtomain 10y ago> - convert x and y from decimal to binary What?! What exactly is at the memory address that you think it's converting?
- pdpi 10y agoI'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--jvMMdUZCy0ETKL7w.png https://d262ilb51hltx0.cloudfront.net/max/800/1*Y5WC--jvMMdU...
- forgotpwtomain 10y agoBut that's only happening in your head. It's an implementation detail of your shell/ide that you are reading numbers in base10.
- pdpi 10y agoFrom 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 10y agoBut 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?
- coinomega 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" 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 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