JavaScript Algorithms - 10 - Power of Two

📱 Follow Codevolution

Power of Two Algorithm
JavaScript Algorithms
Algorithms with JavaScript

[Codevolution]

6:55 - Please consider the example as follows (I've made a mistake on the slide). The code still holds good. In binary, following is the representation.
1 -> 1
2 -> 10
4 -> 100
8 -> 1000
and so on.

[rbgmulmb]

you messed up what binary numbers look like. 4 is not 1000 even if you meant 2^4.
3 is 11 in binary
4 is 100 in binary. It's 2^2
7 is 111 in binary.
8 is 1000 in binary. It's 2^3
and the example should look like:
(2) 10 & (1) 1 = 0
(3) 11 & (2) 10 = 1
(4) 100 & (3) 11 = 0
(5) 101 & (4) 100 = 100
(6) 110 & (5) 101 = 100
(7) 111 & (6) 110 = 110
(8) 1000 & (7) 111 = 0

[prashantbismani]

Here's an Example with breakdown for people who are not clear with bitwise operation

Number: 4 (binary: 0100) - This is the binary representation of the number 4. In binary, it has only one bit set to 1, which is the leftmost bit (the most significant bit).

Subtracting 1 from 4: When we subtract 1 from the number 4, we get 3. Here's how it works in binary:

Number 4 (binary: 0100)
Subtract 1: 4 - 1 = 3 (binary: 0011)
Subtracting 1 from 4 changes the leftmost 1 to 0 but leaves the other bits unchanged.

Bitwise AND Operation (4 & 3): Now, let's perform a bitwise AND operation between the original number 4 and the result of subtracting 1 (which is 3).

Number 4 (binary: 0100)
Number 3 (binary: 0011)
When we perform a bitwise AND operation between these two binary numbers, we compare each bit position:

At the first bit position: 0 & 0 = 0
At the second bit position: 1 & 0 = 0
At the third bit position: 0 & 1 = 0
At the fourth bit position: 0 & 0 = 0
The result of the AND operation is 0000 in binary, which is equal to 0 in decimal.

Result: 4 & 3 = 0: The result of the bitwise AND operation between 4 and 3 is 0. This means that the binary representation of the result has only zeroes, indicating that 4 is indeed a power of two.


And

Number: 3 (binary: 0011) - This is the binary representation of the number 3. In binary, it has two bits set to 1. These are the rightmost bit and the second rightmost bit.

Subtracting 1 from 3: When we subtract 1 from the number 3, we get 2. Here's how it works in binary:

Number 3 (binary: 0011)
Subtract 1: 3 - 1 = 2 (binary: 0010)
Notice that subtracting 1 from 3 sets the rightmost bit (the least significant bit) to 0 and leaves the other bits unchanged.

Bitwise AND Operation (3 & 2): Now, let's perform a bitwise AND operation between the original number 3 and the result of subtracting 1 (which is 2).

Number 3 (binary: 0011)
Number 2 (binary: 0010)
When we perform a bitwise AND operation between these two binary numbers, we compare each bit position:

At the first bit position: 0 & 0 = 0
At the second bit position: 0 & 1 = 0
At the third bit position: 1 & 1 = 1
At the fourth bit position: 1 & 0 = 0
The result of the AND operation is 0010 in binary, which is equal to 2 in decimal.

Result: 3 & 2 = 2: The result of the bitwise AND operation between 3 and 2 is 2. This means that the binary representation of the result has one bit set to 1, which is the second rightmost bit.

[boskoa.]

Binary is base two - every new digit introduced with the rest being zeros represents a number which is a power of two; and every previous number is the largest possible number that can be expressed with one less digit (i.e. all digits are 1). So, the bitwise "and" cancels them out:

2 & 1: 10 1
4 & 3: 100 11
8 & 7: 1000 111
16 & 15: 10000 1111

[nsikakessien]

Thanks sincerely Vishwas for taking time to explain this concept in a very simple way.

[vaibhavsharma]

function isPowerOfTwo(number) {
// If the number is less than 1, it's not a power of two
if (number < 1) {
return false;
}

// Keep dividing the number by 2 until it becomes 1
while (number > 1) {
if (number % 2 !== 0) {
// If the remainder is not zero, it's not a power of two
return false;
}
number /= 2;
}

// If the number becomes 1, it's a power of two
return true;
}

[KamalSingh-zool]

Following code will also have time complexity of O(1)

function isPowerTwo(n) {
if {
return true;
}
return false;
}

console.log(isPowerTwo(8))
console.log(isPowerTwo(16))
console.log(isPowerTwo(5))

[fareedzafar]

Bitwise fried my brain, i will back for bitwise again after completing the playlist or if it is required again in the future videos

[jediofjavascript]

when he asked us to pause and try to solve on our own, i did, and i got a solution with a constant Big-O, but my solution was different to his.
here is my solution

function isPowerOfTwo(n) {
return Math.log2(n) - Math.round(Math.log2(n)) === 0
}
and I didn't need an if statement for "n = 0"
just thought i should share 😊

[noir]

You have the best channel. I'm amazed. Subbed!

[balramagnihotri]

alternate solution:-
function powerOfTwo(n) {
return
}

[emanmkhareez]

This course is very useful, thank you very much

[AkashGauravchannel]

function isPowerOfTwo(n) {
if (n < 0) {
return false
}

while (n % 2 === 0) {
n = n / 2
}

if (n === 1) {
return true
}
return false
}

[shanu]

SOLUTION BY FOR LOOP:

function powerOfTwo(n) {
if (n < 1) {
return false;
}
for (let i = 0; i < n; i++) {
if (n === 2 ** i) {
return true;
}
}
return false;
}

console.log(powerOfTwo(1));
console.log(powerOfTwo(2));
console.log(powerOfTwo(64));
console.log(powerOfTwo(100));

[metaltank]

Sir, the other solution I think with O(1)- constant is
function powerOfTwo(n){
    let power = Math.log(n)/Math.log(2)
    if(Number.isInteger(power)){
        console.log(`${n} is equal to power of ${power}`)
        return true
    } else {
        console.log(`${n} does not exist in power of 2`)
        return false
    }
}

powerOfTwo(1)
powerOfTwo(4)
powerOfTwo(5)

[abhinavprabhakar]

I suppose another way is to take log to the base 2 and check if the answer's an integer?

[gagikyesayan]

Power of Two algorithm I think the best solution is .
function isPowerOfTwo(n){
return Number.isInteger(Math.log(n) / Math.log(2));

}

[rakhmatillorustamov]

Thank you very much!!!. I would like you to make algorithm lessons a lot.

[sandyshan]

Anything wrong with this?
for( let i=0; i< n; i++){
if(Math.pow(2, i) === n){
return true
}
}

[stevesummers]

This is how I worked it out which is also O(1)

function powerOfTwo(n) {
if(n < 1) {
return false;
} else if(Math.log2(n) === Math.round(Math.log2(n))) {
return true;
} else {
return false;
}
}