CODEWITHSUNDEEP
javascriptbit-manipulationincrement
Mike
Mike

Reputation: 3418

How does this function increment?

Can someone explain how the heck below function increments:

function increment (i) {
  i ^= (i & ~-~i) | (~i & -~i)
  return i
}

I think I know javascript, but when I see something above, it pisses me off.

Upvotes: 2

Views: 115

Answers (2)

user555045
user555045

Reputation: 64904

Here's a shorter proof, automatically generated by my website

i ^ (i & ~-~i | ~i & -~i)
definition of xor
i ^ i ^ -~i
xor with self
-~i
definition of two's complement
~~i + 1
double complement
i + 1

In the step "definition of xor", the definition x ^ y = x & ~y | ~x & y is used, with x being i and y being -~i.

In the step "definition of two's complement", the definition -x = ~x + 1 is used, with x being ~i.

Upvotes: 2

Stefano Sanfilippo
Stefano Sanfilippo

Reputation: 33046

Boolean algebra 101.

First, under the assumption that we are working with two's complement, this is the definition of unary minus operator - (see the footnote too):

-A = ~A + 1

Here is your RHS expression, with some extra parenthesis added, without the shortcut assignment and with all operators in extended form for better readability:

i xor ((i and ~(-(~i))) or (~i and -(~i))

We apply the first relation:

i xor ((i and ~(~~i + 1)) or (~i and (~~i + 1))

complement operator ~ is idempotent, meaning that ~~i is equal to i, so we simplify:

i xor ((i and ~(i + 1)) or (~i and (i + 1)))

the second term of the xor operator has the (X and ~Y) or (~X and Y) form, which means "one of X and Y must be true for the expression to be true, but not both", which the very definition of exclusive or (xor), so we can replace that with X xor Y, obtaining:

i xor (i xor (i + 1))

we change the association (xor is associative) and we get:

(i xor i) xor (i + 1)

i xor i is a contradiction (always false), so we get:

false xor (i + 1)

note that the truth value of false xor X depends entirely on X, so we can rewrite the above as:

i + 1

So the RHS evaluates to i + 1. We replace it in the original code and we get:

function increment(i) {
    i = i + 1
    return i
}

Voilà!

NOTE: + should be formalized as another operator if we wanted to be fully formal. In this case, we can safely skip the definition and keep it a black box, since we did not need any of its properties. The only thing that matters is that ~ has a higher priority than +.

Upvotes: 5

Related Questions