Preface 🤹

When we used to do math, we used to have all kinds of idempotent calculations. For example, 40=1; 41 = 4; 42 = 16; 43 = 64; 44 = 256; Calculations like this are idempotent.

So if you put it in front of the program, how do you tell?

🚴 1. Requirement analysis – Determine whether it is idempotent of 4

First of all, what we want to do is, when you enter a number, click judge. If it is a power of 4, the number inside the input box turns green; Otherwise, the number in the input box turns red. As shown below:

So, let’s talk about an implementation from the shallow to the deep.

🤾 2. Implementation version

1. Version 1: Rules and regulations

First attach the code:

HTML code:

<input id="num" value="65536"></input>
<button id="checkBtn">judge</check>
Copy the code

The CSS code:

#num {
  color: black;
}

#num.yes {
  color: green;
}

#num.no {
  color: red;
}
Copy the code

JS code:

funciton isPowerOfFour(num) {
    num = parseInt(num);
   	
    while(num > 1) {
        if(num % 4) return false;
        num /= 4;
    }
    return true;
}
Copy the code

If num is not 0, return false; if num is 0, return false.

If so, divide num by 4 and repeat until num <= 1.

2. Version 2: bitwise and

First attach the code:

HTML code:

<input id="num" value="65536"></input>
<button id="checkBtn">judge</check>
Copy the code

The CSS code:

#num {
  color: black;
}

#num.yes {
  color: green;
}

#num.no {
  color: red;
}
Copy the code

JS code:

function isPowerOfFour(num) {
    num = parseInt(num);
    
    while(num > 1) {
        // Mod 4 is equivalent to judging the last two digits of a binary number
        if(num & 0b11) return false;
        // Shift num two Spaces to the right
        num >>>= 2;
    }
    return true;
}
Copy the code

In the second way we can do bitwise and, mod 4 is the same as judging the last two digits of a binary number, which is 0b11. Then move num two Spaces to the right, num >>>= 2.

Version 3: Bitwise and Optimization

First attach the code:

HTML code:

<input id="num" value="65536"></input>
<button id="checkBtn">judge</check>
Copy the code

The CSS code:

#num {
  color: black;
}

#num.yes {
  color: green;
}

#num.no {
  color: red;
}
Copy the code

JS code:

function isPowerOfFour(num) {
    num = parseInt(num);
    
    return num > 0 &&
        	(num & (num - 1= = =))0 &&
        	(num & 0xAAAAAAAA) = = =0
}
Copy the code

Version two is actually an event complexity of log(n), so we can optimize it further, which is version three above, which is constant complexity O(1).

So the first condition is that num has to be greater than 0.

(num & (num – 1)) === 0. Used to remove the last 1 of the current number after each calculation. If the number has only one 1, filter out the binary number with only one 1 in the number.

The third condition is to judge that the last digit of these numbers cannot have an odd number of 0’s, such as 1, 3, 5, 7, 9, etc.

For this algorithm, the performance is relatively good, the code is relatively simple, so in practical use, or worth using.

Version 4: Regular matching method

First attach the code:

HTML code:

<input id="num" value="65536"></input>
<button id="checkBtn">judge</check>
Copy the code

The CSS code:

#num {
  color: black;
}

#num.yes {
  color: green;
}

#num.no {
  color: red;
}
Copy the code

JS code:

function isPowerOfFour(num) {
    // Convert num to a binary string
    num = parseInt(num).toString(2);
    // Use the regular expression to match the binary string
    return / ^ 1 (? * $/ : 00).test(num);
}
Copy the code

If the size of the calculation is not very large, we can also use regular expressions to deal with it. This method takes advantage of JavaScript’s ability to transform strings and regex to evaluate the idempotence of 4.

Compared with the third method, the time cost is indeed a little more, but still within the acceptable range.

⛹️ 3. Conclusion

In the previous article, we used four methods to solve idempotent problems, including bitwise and optimization with low time complexity, and the concise regular matching method. I don’t know if you’ve got it?

If you think this article is helpful to you, you might as well like to support yo ~~😉

🤼 previous recommendation

👉 Follow the steps of moon Shadow big guy, let’s learn how to write good JS (1)

👉 Follow the steps of moon Shadow big guy to learn how to write good JS (2)

👉 every day in front of the traffic lights shuttle line, how about their own to achieve a traffic light?