Programming Challenge #8 [Beginner]

[r3llun]

Hi everyone, this is my first post and it just happened to come across this problem while I was registering for your forum. So nice to meet you

The problem itself is pretty straightforward. For simplicity I would describe it using C, but I think it is so simple so anybody can implement its solution in every (general purpose) language.

##Problem statement

If I had to give a name to the problem, I would name it convert an integer to its symmetrical binary representation.

Going a bit further, suppose we have an int variable with value of 255, in binary this is 0000 0000 0000 0000 0000 0000 1111 1111 in a machine where int size is four bytes. Now suppose LSB (less significant bit) is placed at index 0, second LSB is placed at index 1 etc. So MSB (most significant bit) is placed at index 31 in that case. What we want, is exchange positions of i and 31-i bits in that case, where i can take values from [0,31]

It is straightforward output should be 1111 1111 0000 0000 0000 0000 0000 0000.

##Implementation

We need to create a function that takes an at least an int as an argument (but this is not a restriction) and returns its binary symmetrical, as described above. Using only binary operators. Ok, if this makes it difficult for you can have a try without this restriction.

##Example

###Sample input-output
(on a 4-byte int machine)

intput: 255
output: 4278190080
input: 98304
output: 98304

##Going a bit further
Try making it work for 33 bits (32-bits + a bit further = 33-bits ). I’m joking.

Try accepting as input not only int types all the numerical types like longs, doubles etc. So the challenge would be to find a more generic solution, that doesn’t depend on the size of the data. In this case I think data size should be provides as input to the function.

#####EDIT: Made some changes to the numbers and the inputs/outputs because I used 16-bits instead of 32.

[M3r8]

isnt it a 4byte int machine?

[Assossa (0x65)]

I wrote my solution in C++ so I can use the magic of templates. The function can mirror the bits of any integer datatype you pass it.

template <class T>
T mirrorNumber(T n) {
	unsigned int bits = sizeof(n) << 3;
	T mirrorN = 0;

	for (unsigned int i = 0; i < bits; i++)
		if (n & (1 << i))
			mirrorN |= 1 << (bits - 1 - i);

	return mirrorN;
}

[oaktree]

I wrote up about the same thing as you… I will say though, that the if is unnecessary:

res |= ( (1 << i) & val ) << (bits - i - 1);

[oaktree]

Output seems wrong. 1111 1111 0000 0000 for int would be negative at the very least…

[Assossa (0x65)]

Oh, yea. I can’t believe I didn’t think of that…

I was using unsigned ints for testing. If you are using signed, then you will end up with a negative number if your starting number is odd.

[Bowlslaw]

Perl master race:

# Return binary representation of each integer, separated by a single space, given as a command line argument.

sub binary {
    my ($n) = @_;
    return $n if $n == 0 || $n == 1;
    
    my $k = int($n / 2);
    my $b = $n % 2;

    my $e = binary($k);

    reverse $e.$b;
}

foreach my $arg(0..$#ARGV) {
    print "${\binary($ARGV[$arg])}\n";
}

[oaktree]

But How about bitwise?

[Bowlslaw]

Oopsie daisie…

[r3llun]

Tbh, when I came across the problem, even the time when I was writing the post I didn’t have realized there exists such a simple solution (so I will change the challenge level to beginner). Good job! Btw I was thinking the there should exist a simple solution for implementing the solution for different numerical types in more languages that it actually seems to.

In C, I found it really difficult to implement such this for the matter of a game. So even the poster couldn’t solve the full challenge But challenge can remain for anybody interested to.

This is the solution I came up with. I 'll call it Mergy-sorty cause it reminds me the Merge-sort

void print(int num) {
    int i;
    int mask = 1<<sizeof(int)*8-1;
    for(i=1; i<=sizeof(int); i++){
        printf("%u",num & mask ? 1 : 0);
        if (i%4 == 0) printf(" ");
        num = num<<1;
    }

    printf("\n");
}

int srl(int num, int sa) {
    return (int)((unsigned int) num >> sa);
}

int reverse(int num, int size, int splits, int mask) {
    int mask2, mask1;
    if (size == splits) {
        return num & mask;
    } else if (splits == 0) {
        splits = 2;
        mask1 = -1<<(size/2);
        mask2 = srl(-1, size/2);

        /*
        printf("mask1 : ");
        print(mask1);
        printf("mask2 : ");
        print(mask2);
        printf("num   : ");
        print(num);
        printf("\n");
        */
        
        return reverse((num<<(size/splits)) & mask1, size, splits, mask1) ^ reverse(srl(num, size/splits) & mask2, size, splits, mask2);
    } else {
        splits *= 2;
        mask1 = (mask<<(size/splits)) & mask;
        mask2 = srl(mask, size/splits) & mask;

        /*
        printf("mask1 : ");
        print(mask1);
        printf("mask2 : ");
        print(mask2);
        printf("num   : ");
        print(num);
        printf("\n");
        */
        
        return reverse((num<<(size/splits)) & mask1, size, splits, mask1) ^ reverse(srl(num, size/splits) & mask2, size, splits, mask2);
    }
}

####Tip :
Out-comment the print statements to unveil the magic