Oneliners (C++, Java, Ruby, Python)


  • 24

    Solution 1 - Cancel Bits

    bool hasAlternatingBits(int n) {
        return !((n ^= n/4) & n-1);
    }
    

    Xor the number with itself shifted right twice and check whether everything after the leading 1-bit became/stayed 0. Xor is 0 iff the bits are equal, so we get 0-bits iff the pair of leading 1-bit and the 0-bit in front of it are repeated until the end.

        000101010
      ^ 000001010
      = 000100000
    

    Solution 2 - Complete Bits

    bool hasAlternatingBits(int n) {
        return !((n ^= n/2) & n+1);
    }
    

    Xor the number with itself shifted right once and check whether everything after the leading 1-bit became/stayed 1. Xor is 1 iff the bits differ, so we get 1-bits iff starting with the leading 1-bit, the bits alternate between 1 and 0.

        000101010
      ^ 000010101
      = 000111111
    

    Solution 3 - Positive RegEx

    public boolean hasAlternatingBits(int n) {
        return Integer.toBinaryString(n).matches("(10)*1?");
    }
    

    It's simple to describe with a regular expression.

    Solution 4 - Negative RegEx

    def has_alternating_bits(n)
      n.to_s(2) !~ /00|11/
    end
    

    It's even simpler to describe what we don't want: two zeros or ones in a row.

    Solution 5 - Negative String

    def hasAlternatingBits(self, n):
        return '00' not in bin(n) and '11' not in bin(n)
    

    Same as before, just not using regex.

    Solution 6 - Golfed

    def has_alternating_bits(n)
      (n^=n/2)&n+1<1
    end
    

    Solution 7 - Recursion

    def has_alternating_bits(n)
      n < 3 || n%2 != n/2%2 && has_alternating_bits(n/2)
    end
    

    Compare the last two bits and recurse with the last bit shifted out.

    Solution 8 - Complete Bits + RegEx

    public boolean hasAlternatingBits(int n) {
        return Integer.toBinaryString(n ^ n/2).matches("1+");
    }

  • 0

    Love your negative regex solution!


  • 1
    S

    Here is my stab on this problem

    In either n^(n<<1) or n^(n>>1) should set all bits set from most significant bit onwards. Adding 1 to it makes it power of 2

    class Solution(object):
        def hasAlternatingBits(self, n):
            """
            :type n: int
            :rtype: bool
            """
            
            aux = 0
            if n & 1:
                aux = ( n ^ (n<<1) ) + 1
            else:
                aux = ( n ^ (n>>1) ) + 1
            
            return aux & (aux-1) == 0
    

  • 1

    All your solutions are a BIT too short.

    I'm glad even I came up with xor toggle solution :D

    public boolean hasAlternatingBits(int n) {
        int prev = n & (1);
        n >>= 1;
        while(n > 0) {
            if(((n & 1) ^ prev) == 0) return false;
            prev = n & 1;
            n >>= 1;
        }
        return true;
    }

  • 2
    J

    @StefanPochmann said in Oneliners (C++, Java, Ruby, Python):

    ((n ^= n/4) & n-1);

    I think !((n ^= n/4) & n-1) is undefined behavior. I would rather split it in two statements:
    n ^= n >> 2;
    return !(n & (n - 1));


  • 0

    @chris.rocco7 said in Oneliners (C++, Java, Ruby, Python):

    Love your negative regex solution!

    It's actually my favorite. So simple. And in Ruby it has the advantage that !~ already gives me a boolean, whereas =~ gives me an index or nil, which I'd then have to convert to boolean myself.


  • 0

    @john700 said in Oneliners (C++, Java, Ruby, Python):

    @StefanPochmann said in Oneliners (C++, Java, Ruby, Python):

    ((n ^= n/4) & n-1);

    I think !((n ^= n/4) & n-1) is undefined behavior. I would rather split it in two statements:
    n ^= n >> 2;
    return !(n & (n - 1));

    Yeah, I think you're right. I probably should've used a language where it's not undefined :-)


  • 0
    F

    I've been coding from 5-6 years and all your solutions look like a different language all together.. You're great...


  • 0
    D

    Nice! Gheez, so simple, wow.


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.