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

Topic describes

This is the 693. Alternate binary number on LeetCode. The difficulty is simple.

Tag: analog, bit operation

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

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

Example 3:

Input: n = 11 Output: false Description: the binary representation of 11 is: 1011.Copy the code

Tip:


  • 1 < = n < = 2 31 – 1 1 <= n <= 2^{31} – 1

traverse

According to the meaning, each bit of NNN is traversed.

Code:

class Solution {
    public boolean hasAlternatingBits(int n) {
        int cur = -1;
        while(n ! =0) {
            int u = n & 1;
            if ((cur ^ u) == 0) return false;
            cur = u; n >>= 1;
        }
        return true; }}Copy the code
  • Time complexity: O(log⁡n)O(\log{n})O(logn)
  • Space complexity: O(1)O(1)O(1)

An operation

A more subtle approach is to take advantage of alternating binary properties.

When the given value NNN is an alternate binary number, shift NNN one bit to the right and the value MMM is still the alternate binary number, and the original number NNN is staggered one bit. 11110000… 11110000… The result of 1111 is XXX, in which the addition (carry operation) to XXX results in something like 0000… 100000000… 100000000… The result of 10000, and the execution of this result with XXX bitwise can get full 000 results.

Code:

class Solution {
    public boolean hasAlternatingBits(int n) {
        int x = n ^ (n >> 1);
        return (x & (x + 1)) = =0; }}Copy the code
  • Time complexity: O(1)O(1)O(1)
  • Space complexity: O(1)O(1)O(1)

The last

This is the No.693 of our “Brush through LeetCode” series, which started on 2021/01/01. There are 1916 topics in LeetCode by the start date, some of which have locks, we will first finish all the topics without locks.

In this series of articles, in addition to explaining how to solve the problem, I will also present the most concise code possible. If a general solution is involved, the corresponding code template will also be used.

In order to facilitate the students to debug and submit the code on the computer, I set up the relevant warehouse: github.com/SharingSour… .

In the repository, you’ll see links to the series of articles, the corresponding code for the series of articles, the LeetCode source links, and other preferred solutions.