[10/19/15] Flip Flop

Discussion in 'Programming' started by BlizzardFyre, Oct 19, 2015.

  1. Hello World!

    This is week three of the programming challenge of the week.

    This weeks challenge: Write a method that returns the bit opposite of the number passed in. The function shall be called flip and take an integer as a parameter and return an integer (int flip(int n) { // do stuff }). The catch is you can't use any bitwise or bit shift operators.

    Example:

    flip(10); returns 5.
    flip(17) will return 14

    Explanation 1: 10 is 1010 in binary, and when you flip the values it will be 0101, which is 5.
    Explanation 2: 17 is 10001 in binary, and when you flip the values it will be 01110, which is 14.

    The rules are posted here.

    You may use any method you want as long as it does not use any of the bitwise or bit shift operators.

    EDIT: Clarification, I am assuming that two's complement is not a thing, so use pure binary, not computing binary. Also, only use the digits that are significant, meaning from the left most 1 to the far right digit.

    Submissions close 10/26/15

    Happy Golfing!
     
    #1 BlizzardFyre, Oct 19, 2015
    Last edited: Oct 21, 2015
  2. samczsun

    Supporter

    Code (Text):

    public int flip(int i){int b=1;while(b<=i)b*=2;return b-i-1;}
     
    61 chars in Java
     
    #2 samczsun, Oct 19, 2015
    Last edited: Oct 20, 2015
  3. konsolas

    Supporter

    Does this work? Haven't tested.

    Code (Text):
    public int flip(int i){return -i-1;}
    EDIT: It works, but it flips all bits including leading 0s, like @samczsun 's solution. You didn't specify that. (tested against ~i)
     
    #3 konsolas, Oct 19, 2015
    Last edited: Oct 19, 2015
    • Like Like x 1
    • Winner Winner x 1
  4. Java handles int's as 32 bits. You'd have to apply a mask if you only wish to keep the used amount of bits.
    Also
    Code (Java):
    Integer.reverse(x);
    technically fails to comply with the banned usage of bit operations. (reason I say technically, is that one can argue that its under the hood, and I didn't include the bit operations in my code) Its reader discretion for such a rule.

    Code (Scala):

    import scala.{Int => I}
    import java.lang.Integer.{parseInt => p, reverse => r, toBinaryString => b}

    def main(args: Array[String]): Unit = {
    val x = 10
    val flip = f(x)
    val flip2 = r(x) //this is the exact same as the solution given by @samczsun
    val flip3 = x f
    }
    def f(x:I)=p(b(x)map{case'0'=>'1';case'1'=>'0'},2)
    implicit class BI(x:I){def f=p(b(x)map{case'0'=>'1';case'1'=>'0'},2)}
     
    Of course this golf'd code makes use of scala's import renaming. It's also a solution that completely avoids bit operations.

    Only flip and flip3 assignment lines don't use underlying bit operations.

    50chars
    Code (Scala):
    def f(x:I)=p(b(x)map{case'0'=>'1';case'1'=>'0'},2)
     
    #4 not2excel, Oct 20, 2015
    Last edited: Oct 20, 2015
  5. Code (Text):
        public static void main(String[] args) {
            int num = 10;
           
            System.out.println(num + " flipped to " + flip(num));
        }

        public static int flip(int num){
            return Integer.parseInt(rotateString(Integer.toString(num,2)), 2);
        }
       
        public static String rotateString(String str){
            String strr = "";
            int i=str.length() - 1;
            while(i != -1){
                strr += str.substring(i, i + 1);
                i--;
            }
            return strr;
        }
     
  6. samczsun

    Supporter

    @not2excel I've written a technically non-bitwise solution :)
     
  7. konsolas

    Supporter

    @not2excel @BlizzardFyre

    Could we have some clarification on whether we need to flip all bits, or only starting from the first significant bit?
     
  8. Code (Text):

    int flip(int n){char[]a=Integer.toString(n,2).toCharArray();boolean f=false;for(int i=0;i<a.length;i++){if(!f)if(a[i]=='0')continue;else f=!f;a[i]=a[i]=='0'?'1':'0';}return Integer.parseInt(new String(a),2);}
     
     
  9. From his question and from his examples, it seems only the used bits are what he wants flipped.

    Thats why I had the parentheses. As its reader discretion. xd
     
  10. From ashes i rise to yet again blow away the other entries:

    45 characters, 52 if you need public but that wasn't specified this time.
    Code (Text):
    int flip(int i){return i<0?-i-1:flip(i*2)/2;}
    Shift the number all the way to the left, flip all it's bits, then drop all the 1s you just added by multiplying by 2.
     
    • Winner Winner x 3
    • Like Like x 1
  11. To everyone, a clarification. I am only wanted the significant digits flipped, so from the furthest left 1 to the far right. Also, I am assuming two's complement is not a thing, meaning this is pure binary not computing binary.

    I also edited my original post to reflect this.
     
  12. Time is over...
    Who is the winner? Where is the next challenge?
    It's alredy tuesday.
     
  13. Apologies for the delay! Real life stuff got me held up.

    The winner of this week's challenge is @CrypticStorm.

    Check my main thread for the next challenge, it will be up very soon.