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

Day 75 2021.03.28

693. Alternate binary numbers

  • Leetcode: leetcode-cn.com/problems/bi…
  • Difficulty: Easy
  • Method: bit operation

Topic describes

  • 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.

The sample

  • Example 1
Input: n = 5 Output: true Description: Binary representation of 5 is: 101Copy the code
  • Example 2
Input: n = 7 Output: false Description: binary representation of 7 is: 111.Copy the code

Their thinking

Similar topic

  • The number of ones

Conventional simulation

  • After converting the current decimal number to a binary number, separate the next and previous digits and compare them. If the two bits are always the same, the matching alternate binary number is returnedtrue; Reverse direct returnfalse
  • The initial idea: the modulo gets the last digit, no two digits are compared as a group, and if one of the groups does not meet the requirements, then returnfalse; On the contrary, if there is no inconsistency found all the time, returntrue
  • Then you just need to use the xOR operator to determine whether it matches
    • Different or 1
    • Same xOR, 0

Late optimization

  • Get the last digit each time (0 or 1), do not need to use modular arithmetic, can use&Bit and operation
  • For example:
    • 111-1 & = 1
    • 110-1 & = 0
  • Summary: the bitwise and is used to determine the last digit is0 or 1the
  • In terms of speed, bit operation is superior to modular operation.

Another bit operation

  • The inputnThe binary representation of the right after moving one digit, the resulting number and againnBitwise xor obtaineda. If and only if inputnIs an alternate binary number,aThe binary representation of1(Not including the lead0). Here’s a simple proof: whenaA certain digit of is1, if and only ifnThe corresponding bit of is different from its predecessor. whenaEach digit of1, if and only ifnIs different from all adjacent bits of, i.enIs an alternate binary number.
  • willa 与 a + 1Bitwise and, if and only ifaThe binary representation of1, the result is0. Here’s a simple proof: if and only ifaThe binary representation of1When,a + 1Can carry, and the original highest position is0The result of bitwise and is0. Otherwise, no carry is generated, and both the highest bits are1And the result is not0. Combined with the above two steps, you can determine whether the input is an alternate binary number.

ACcode

var hasAlternatingBits = function(n) {
  let contra = n % 2;
  n = n >> 1;
  while(n) {
    let wei = n % 2;
    if(! ((wei) ^ contra)){return false;
    }
    // console.log('contra:', contra)
    contra = wei;
    n = n >> 1;
  }
  return true;
};
Copy the code

New bitwise operations

var hasAlternatingBits = function(n) {
    const a = n ^ (n >> 1);
    return (a & (a + 1= = =))0;
};
Copy the code

conclusion

  • The shift operator is, in essence, faster thann / 2the
    • The shift operator =parseInt(n / 2)