In binary, convert from signed-magnitude to two’s-complement. All in C

Question

I have an interesting puzzle. I need to convert from a signed number, say -5 (0x80000005) to two’s complement -5 (0xFFFFFFFB). The only operators I can use are, !, ~, &, ^, |, +, <<, >> and at most 15 of them in any combination with as many variables as I want. = may be used and does not count towards the total number of operators. Also, no “if” statements, loops or calls to functions of any kind may be used.

the function will look like

int sign2two(int x){
//... some stuff here
return x;
}

The problem I am having is that I can find out if the number is negative. But I want to say, if num is negative then flip bits and add 1. Otherwise return number. And I can’t figure out how to do that. Thanks.

Answer 1

To convert from Sign Magnitude x to Two's Complement y:

1) On a two's complement machine.
2) Uses only !, ~, &, ^, |, +, <<, >>
3) Does not use ?:, -, *, /
4) Does not assume 4-byte int
5) Works with all Sign Magnitude integers including +0 and -0

#include <limits.h>
int sm2tc(int x) {
  int sign = x & INT_MIN;
  int negmask = UINT_MAX + !sign;
  return (x & ~negmask) | (negmask & ((~x + 1)^INT_MIN));
}

This answer is to a duplicate question How to convert from sign-magnitude to two's complement whose selected answer did not meet the OP's stated criteria considering operation restriction.

Answer 2

These problems are extremely dumb in my opinion...

#include <stdint.h>
#include <stdio.h>

int32_t test1(uint32_t x) {
    const uint32_t sign  = (x & 0x80000000); // Total operations: 1
    const uint32_t value = (x & 0x7FFFFFFF); // Total operations: 2

    // Let's create a value N, where N is equal to:
    // if (sign)
    //     N = 0xFFFFFFFF;
    // else
    //     N = 0x00000000;
    uint32_t N = sign;  // Total operations: 2
    N = N | (N >> 1);   // Total operations: 4 
    N = N | (N >> 2);   // Total operations: 6
    N = N | (N >> 4);   // Total operations: 8
    N = N | (N >> 8);   // Total operations: 10
    N = N | (N >> 16);  // Total operations: 12

    // Let's create a value MaybeOne, where MaybeOne is equal to:
    // if (sign)
    //     MaybeOne = 1;
    // else
    //     MaybeOne = 0;
    uint32_t MaybeOne = N & 0x1; // Total operations: 13

    // Now, Let's perform the following step:
    // if (sign)
    //     return (value ^ 0xFFFFFFFF) + 1;
    // else
    //     return (value ^ 0x00000000) + 0;
    return (value ^ N) + MaybeOne; // Total operations: 15
}

int32_t test2(uint32_t x) {
    int32_t sign = (x & 0x80000000);
    int32_t value = (x & 0x7FFFFFFF);

    if (sign)
        return -value;
    else
        return value;
}

int main() {
    uint32_t i;
    for (i=0; i<0xFFFFFFFF; ++i) 
        if (test1(i) != test2(i))
            printf("0x%08x\n", i);
}

---

Additionaly, using a comment from Eric Postpischil, we can reduce the number of operations significantly:

int32_t test3(uint32_t x) {
    const uint32_t sign  = (x >> 31);        // Total operations: 1
    const uint32_t value = (x & 0x7FFFFFFF); // Total operations: 2

    // Let's create a value N, where N is equal to:
    // if (sign)
    //     N = 0xFFFFFFFF;
    // else
    //     N = 0x00000000;
    const uint32_t N = ~sign + 1;  // Total operations: 4

    // Let's create a value MaybeOne, where MaybeOne is equal to:
    // if (sign)
    //     MaybeOne = 1;
    // else
    //     MaybeOne = 0;
    uint32_t MaybeOne = sign; // Total operations: 4

    // Now, Let's perform the following step:
    // if (sign)
    //     return (value ^ 0xFFFFFFFF) + 1;
    // else
    //     return (value ^ 0x00000000) + 0;
    return (value ^ N) + MaybeOne; // Total operations: 6
}

Answer 3

You have no conditionals available but you can mask. There are different ways of creating a mask dependent on the value of the sign.

The following uses very nice tips by Eric Postpischil!

If the sign is 0 (ie positive) then the mask will become 0, else it is still the value you need -> conditional without conditional

#include <stdarg.h>
#include <stdio.h>
int sign2two(unsigned int a){
    int sign = a>>31; // alternative: sign = !!((a<<1>>1)+~a+1);  see below
    unsigned int withoutSign = a << 1 >> 1;
    unsigned int mask = ~sign +1;
    printf("withoutSign is: %u\nsign is: %u\nmask is: %x\n", 
        withoutSign, sign, mask);
    unsigned int temp = (withoutSign^mask)+sign;
    return *(int*)&temp;
}
void printSign2two(unsigned int a){
    printf("the 2s complement number: %i\n\n", sign2two(a));
}
int main(){
    printSign2two(0x00000005);
    printSign2two(0x80000005);
    return 0;
}

output:

withoutSign is: 5
sign is: 0
mask is: 0
the 2s complement number: 5

withoutSign is: 5
sign is: 1
mask is: ffffffff
the 2s complement number: -5

Note about the sign = !!((a<<1>>1)+~a+1);. This uses some more operators than sign = a>>31 but it is independent of 32/64 bitness.

• <<1>>1 clears the most significant bit,
• we then want to check if it is different than the original. since -a is not allowed we use +~a+1 (thanks again Eric Postpischil)
• if there is no difference we already have the value 0 we want, else we have some huge number
• we then use !! to change the huge number to 1.