LeetCode - Easy - 693. Binary Number with Alternating Bits

我不是女神ヾ 2022-11-17 03:22 103阅读 0赞

## Topic ##

*  Bit manipulation

## Description ##

[https://leetcode.com/problems/binary-number-with-alternating-bits/][https_leetcode.com_problems_binary-number-with-alternating-bits]

Given a positive integer, check whether it has alternating bits: namely, if two adjacent bits will always have different values.

**Example 1:**

Input: n = 5
    Output: true
    Explanation: The binary representation of 5 is: 101

**Example 2:**

Input: n = 7
    Output: false
    Explanation: The binary representation of 7 is: 111.

**Example 3:**

Input: n = 11
    Output: false
    Explanation: The binary representation of 11 is: 1011.

**Example 4:**

Input: n = 10
    Output: true
    Explanation: The binary representation of 10 is: 1010.

**Example 5:**

Input: n = 3
    Output: false

**Constraints:**

*   1 < = n < = 2 31 − 1 1 <= n <= 2^\{31\} - 1 1<=n<=231−1

## Analysis ##

方法一：我写的。思路就是将数转换成二进制形式，检测**两两相邻数位是否相同**，若有相同，则返回false，没有的，则返回true。

方法二：别人写的。[link][]

![c2c4379bce633d047fad0ee44d8b67ca.png][]

## Submission ##

public class BinaryNumberWithAlternatingBits { 
    
    	// 方法一：我写的
    	public boolean hasAlternatingBits(int n) { 
    		int first = n & 1, second;
    		n >>= 1;
    		while (n != 0) { 
    			second = n & 1;
    			if (first == second)
    				return false;
    			first = second;
    			n >>= 1;
    		}
    		return true;
    	}
    
    	// 方法二：别人写
    	public boolean hasAlternatingBits2(int n) { 
    		n = n ^ (n >> 1);
    		return (n & n + 1) == 0;
    	}
    
    }

## Test ##

import static org.junit.Assert.*;
    import org.junit.Test;
    
    public class BinaryNumberWithAlternatingBitsTest { 
    
    	@Test
    	public void test() { 
    		BinaryNumberWithAlternatingBits obj = new BinaryNumberWithAlternatingBits();
    
    		assertTrue(obj.hasAlternatingBits(5));
    		assertFalse(obj.hasAlternatingBits(7));
    		assertFalse(obj.hasAlternatingBits(11));
    		assertTrue(obj.hasAlternatingBits(10));
    		assertFalse(obj.hasAlternatingBits(3));
    
    		assertTrue(obj.hasAlternatingBits2(5));
    		assertFalse(obj.hasAlternatingBits2(7));
    		assertFalse(obj.hasAlternatingBits2(11));
    		assertTrue(obj.hasAlternatingBits2(10));
    		assertFalse(obj.hasAlternatingBits2(3));
    	}
    }

[https_leetcode.com_problems_binary-number-with-alternating-bits]: https://leetcode.com/problems/binary-number-with-alternating-bits/
[link]: https://leetcode.com/problems/binary-number-with-alternating-bits/discuss/113933/Java-super-simple-explanation-with-inline-example
[c2c4379bce633d047fad0ee44d8b67ca.png]: /images/20221022/68f2395a527d423c97834457853f7ac0.png