News for hackers. Stuff that matters.
Re:The beauty of bitwise AND by thedufer on Thursday August 04, 2016 @01:48AM (#12223649)
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.
Re:The beauty of bitwise AND by Strilanc on Thursday August 04, 2016 @02:04AM (#12223704)
> 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

Re:The beauty of bitwise AND by thedufer on Thursday August 04, 2016 @08:21AM (#12224995)
The laws given in the post were explicitly derived from the equation. Please explain how you used that to determine f(0, -1)?
Re:The beauty of bitwise AND by Strilanc on Thursday August 04, 2016 @11:17AM (#12226061)
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
Re:The beauty of bitwise AND by thedufer on Friday August 05, 2016 @01:09AM (#12230174)
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?
Re:The beauty of bitwise AND by Strilanc on Sunday August 07, 2016 @04:07PM (#12243417)
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
Re:The beauty of bitwise AND by TTPrograms on Thursday August 04, 2016 @03:11AM (#12223935)
I'm not quite sure they have enough paper for numbers with infinite boolean expansions.