Offer to come, dig friends take it! I am participating in the 2022 Spring Recruit Punch card activity. Click here for details.

preface

Today’s topic is simple, the topic itself is not difficult, even can play a little clever, but really need to learn and master, is an understanding of bit operations.

A daily topic

Today’s topic is 693. Alternating binary numbers. The difficulty is simple

  • Given a positive integer, check whether its binary representation always alternates zeros and ones: in other words, the two adjacent digits in the binary representation are never the same.

Example 1:

Enter n =5Output:trueExplanation:5The binary representation of is:101
Copy the code

Example 2:

Enter n =7Output:falseExplanation:7The binary representation of is:111.
Copy the code

Example 3:

Enter n =11Output:falseExplanation:11The binary representation of is:1011.
Copy the code

 

Tip:

  • 1 <= n <= 231 – 1

Answer key

The real violent solution 😂

Local due to the test data is limited, can use the real violence solution – directly enumerate all the data into an array, see if the problem given n exists in the array, can get the number that meets the problem requirements.

/ * * *@param {number} n
 * @return {boolean}* /
var hasAlternatingBits = function (n) {
  return([1.2.5.10.21.42.85.170.341.682.1365.2730.5461.10922.21845.43690.87381.174762.349525.699050.1398101.2796202.5592405.11184810.22369621.44739242.89478485.178956970.357913941.715827882.1431655765,
    ].indexOf(n) + 1
  );
};
Copy the code

Loop simulation

How to figure out what the binary of a decimal number is, the principle is very simple, we keep dividing the number by two, each time the remainder is the current binary, until it is 1, and then we get the binary of a number.

According to this principle, we just have to keep dividing the number by two to get the remainder of each loop, the current base bit, and the remainder of the last loop. If it’s not the other way around, we’ll return false. If it doesn’t return false at the end of the loop, we’ll return true

/ * * *@param {number} n
 * @return {boolean}* /
var hasAlternatingBits = function(n) {
    let yushu
    while(n ! = =0) {
        const cur = n % 2;
        if (cur === yushu) {
            return false;
        }
        yushu = cur;
        n = Math.floor(n / 2);
    }
    return true;
};
Copy the code

An operation

Let’s take 5, binary 101, for example.

When the input number is good enough for the problem, like 101. We move it one place to the right, we get 10, so it’s xor with the original number, xor is the same digit, both 0, different 1, so you get a binary that’s both 1’s

And then a binary that’s all made up of 1’s, how do we quickly tell if it’s all 1’s? The answer is simple, add one to it, and then take the sum of the original numbers, and if it’s 0 then it means that the original numbers are all 1’s and vice versa.

If I have a number 111, if I add one to it and I get 1000 then I get 0.

/ * * *@param {number} n
 * @return {boolean}* /
var hasAlternatingBits = function(n) {
    const a = n ^ (n >> 1)
    return (a & (a + 1= = =))0
}
Copy the code