How does bitwise operation work on Booleans?

Question

I came across this challenge on Edabit and couldn't work out this bitwise operation solution.

notNotNot = (a,b) => !!(a%2 >> b)

The challenge:

//Something which is not true is false, but something which is not not true is true! 
//Create a function where given n number of "not", evaluate whether it's true or false.

//Examples:
notNotNot(1, true) ➞ false
// Not true

notNotNot(2, false) ➞ false
// Not not false

notNotNot(6, true) ➞ true
// Not not not not not not true

I did some research that that operator:

Shifts right by pushing copies of the leftmost bit in from the left, and let the rightmost bits fall off.

That I reckon I understood (e.g. 5 >> 1 same as 0101 >> 1 which evaluates to 0010), but I can't see how that works with a boolean? I know true evaluates to 1 and false to 0.

Answer 1

The function you gave does not satisfy the challenge. Right shifting will not do what is asked for. For example, your notNotNot(6,true) is false, not true when put through your function.

Your question is about bitwise operation on a boolean though. Since operators like >> and << work on integers, Javascript first converts the boolean value to an integer. So true becomes 1 and false becomes 0. To see this you can shift by zero:

console.log("true is",true >> 0)
console.log("false is", false >> 0)

So bitwise operation on booleans is really just bitwise operation on either 0 or 1.

Using !! is a handy way to convert anything into a boolean. It takes anything that would be considered equivalent to false (such as 0, null, undefined or "") and gives back false. Similarly anything that is truthy (like 14, "hello", [4], {a:1}) and give back true. !! works because the first exclamation mark gives the 'not' of the expression which is always true or false, then the second exclamation mark gives the opposite of that (false or true).

Getting back to the challenge, it wants to apply the not-operator 'a' times and compare to the 'b' value. So something like this would work:

function notNotNot(a, b) { return !!(a%2 - b); }
console.log("notNotNot(1, true)",notNotNot(1, true));
console.log("notNotNot(2, false)",notNotNot(2, false));
console.log("notNotNot(6, true)",notNotNot(6, true));

Answer 2

Bitwise operators always convert their operands to an integer. So, 4 >> true is the same as 4 >> 1 which will do a bit shift right by one position

(decimal) 4 = (binary) 100

(binary) 100 >> 1 = (binary) 010

(binary) 010 = (decimal) 2

console.log(4 >> true);

So, using true or false is a just a roundabout way to use 1 or 0.

The notNotNot function has very simple operation, overall:

1. a%2 converts the first number into 0 for even or 1 for odd.
2. >> b shifts right by either 0 positions for false or 1 position for true.
   • a is odd (1) and b is false = 1
     • there is zero shifts to the right, so the number remains the same.
   • a is odd (1) and b is true = 0
     • the only set bit 1 is shifted right and discarded.
   • a is even (0) and b is false = 0
     • there is zero shifts to the right, so the number remains the same.
   • a is even (0) and b is true = 0
     • the base number is 0 which doesn't have any bits set, so shifting right any amount does not change it.
3. !!() converts the result to boolean.

With that said, the solution here is wrong, since notNotNot(2, true) will produce false - a is even and b is true. The expectation is that it will produce true since !!true = true. The same problem is present for any even number and true.

It can be easily fixed by using bitwise XOR instead of right shift:

• a is odd (1) and b is false = 1
  • both match, so they are flipped to 0
• a is odd (1) and b is true = 0
  • they don't match, so we get 1
• a is even (0) and b is false = 0
  • both match, so we get 0
• a is even (0) and b is true = 1
  • they don't match, so we get 1

notNotNot = (a,b) => !!(a%2 ^ b);

console.log("!!true = ", notNotNot(2, true))
console.log("!!!true =", notNotNot(3, true))
console.log("!!false = ", notNotNot(2, false))
console.log("!!!false = ", notNotNot(3, false))

//bonus
console.log("true = ", notNotNot(0, true))
console.log("false = ", notNotNot(0, false))

Just for completeness sake, in case you want a fully bitwise operation:

The modulo operation %2 can be changed to a bitwise AND &1 get the lowest bit. For even numbers, this would yield 0 since you'd be computing

xxx0
&
0001

which is zero. And for odd numbers the same applies but you'd get one as a result:

xxx1
&
0001

So the results of a&1 and a%2 are identical. Furthermore, even though bitwise operations convert the number to a 32-bit signed integer that doesn't matter as the parity would be preserved.

//larger than 31 bits
const largeValue = 2**31 + 1;
//larger than 32 bits
const veryLargeValue = 2**32 + 1

console.log("2**31 + 1 =", largeValue);
console.log("2**32 + 1 =", veryLargeValue);

console.log("2**31 + 1 to 32-bit signed integer =", largeValue | 0);
console.log("2**32 + 1 to 32-bit signed integer = ", veryLargeValue | 0);

const isOddModulo = number => 
  console.log(`(${number} % 2) can detect an odd number: ${(number % 2) === 1}`);

const isOddBitwise = number => 
  console.log(`(${number} & 1) can detect an odd number: ${(number & 1) === 1}`);

isOddModulo(largeValue);
isOddBitwise(largeValue);

isOddModulo(veryLargeValue);
isOddBitwise(veryLargeValue);

Answer 3

Lets analysis solution first

notNotNot(oddNumber, true)  ➞ false
notNotNot(evenNumber, true) ➞ true

notNotNot(oddNumber, false)  ➞ true
notNotNot(evenNumber, false) ➞ false

Now analysis the for (a,b) => !!(a%2 >> b)

a%2 == 0 ➞ even number
a%2 == 1 ➞ odd number

// For a%2 == 0

a%2 >> b ➞ if b is true  ➞ 0 >> 1 ➞ 0   // Not working
a%2 >> b ➞ if b is false ➞ 0 >> 0 ➞ 0


// For a%2 == 1

a%2 >> b ➞ if b is true  ➞ 1 >> 1 ➞ 0
a%2 >> b ➞ if b is false ➞ 1 >> 0 ➞ 1

Thats means this is not working for notNotNot(6, true) is true but current solution gives false.

We can you ^(XOR) operator to make it correct Like (a,b) => !!(a%2 ^ b)

Now analysis the for (a,b) => !!(a%2 ^ b)

a%2 == 0 ➞ even number
a%2 == 1 ➞ odd number

// For a%2 == 0

a%2 ^ b ➞ if b is true  ➞ 0 ^ 1 ➞ 1   // Now working
a%2 ^ b ➞ if b is false ➞ 0 ^ 0 ➞ 0


// For a%2 == 1

a%2 ^ b ➞ if b is true  ➞ 1 ^ 1 ➞ 0
a%2 ^ b ➞ if b is false ➞ 1 ^ 0 ➞ 1

!(a%2 ^ b) use `!` to make int as boolean but solution result will reversed then
!!(a%2 ^ b) use `!` again to reversed it again and make it correct.

Example:

notNotNot = (a,b) => !!(a%2 ^ b);

console.log("!!!!true = ", notNotNot(4, true))
console.log("!!!!false = ", notNotNot(4, false))
console.log("!!!true =", notNotNot(3, true))
console.log("!!!false = ", notNotNot(3, false))

Answer 4

I see that your task is:

/* Create a function where given n number of "not",
   evaluate whether it's true or false.*/

I don't know why you are writing notnotnot function for me that is not what the task asks.

So according to the task I made that function not that accepts a number of "nots" and evaluates them.

The first way

function not(n) {
  return Boolean(n - n - 1);
}

The second way using XOr(^)

function not(n) {
  return Boolean(bool ^ (bool - 1));
}

The third way using Mod(%) pointed by @VLAZ

function not(n) {
  return Boolean(n % 2);
}

The fourth way using bitwise And(&)

function not(n) {
  return Boolean(n & 1);
}

Test

not(0)
//> false 
not(1)
//> true
not(2)
//> false
not(515)
//> true

Answer 5

Firstly, (a,b) => !!(a%2 >> b) does not match the results of the examples. I will break down exactly what it's doing using notNotNot(6, true) ➞ true.

• Fist a%2, simply get a divide by 2 return the remainder. So we will get 0 for an even number and 1 for an odd number. a = 6 a%2 = 0 in this case.
• Then 0 >> b shift 1 number off from the right because as you said true evaluates to 1. So we get 0 >> 1 = 0.
• Last !!(0), is simple, and can be broken down like so, !0 = true, then !true = false.

So if we think about this as long as b is true, we will always get returned false. Let's say we have a = 5, b = true evaluating to 5%2 = 1, 1 >> 1 = 0. You can see because of the mod (%2) we will only ever have 1 or 0 (only ever have 1 digit) and true will always shift off the 1 when we have it.

A simple way to look at this problem is like an isEvenOrNot function. So a is the number we are checking and b is a boolean to check if it's even (true) or not even (false). This works because every second not added will be true.

So a solution using bitwise could be something like: (a,b) => !!(a&1 ^ b). I will let you have the fun of breaking down why it works! :)

A little bit more into explaining how shift works with a boolean. So true as you said will be 1 and false will be 0. So as shown in your example, 0101 >> true is the same as 0101 >> 1.

I hope this helps.

I used the following as a reference for bitwise: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Operators/Bitwise_Operators

Answer 6

(a%2)  //ignore all but the least significant bit (LSB)
(a%2 >> b )  //if TRUE,  shifts right, resolves to 0
               //if FALSE, no shift,     resolves to LSB

// 0 and LSB are both integers so convert to boolean by using logical/boolean NOT
!(a%2 >> b ) //resolves to the boolean which it is NOT
!!(a%2 >> b ) //resolves to the boolean which it is NOT NOT

NB For either boolean, an even number of NOTs results in the original boolean an odd number of NOTs results in the opposite boolean

The LSB of any number dictates whether the number is odd or even.(0 even, 1 odd)