func hasAlternatingBitsNaive(n int) bool {
	for mask := ^(n & 1); n != 0; n >>= 1 {
		next := n & 1
		if mask == next {
			return false
		}
		mask = next
	}
	return true
}

func hasAlternatingBits(n int) bool {
	for n ^= n >> 1; n != 0 && n&1 == 1; n >>= 1 {
	}
	return n == 0
}