CODEWITHSUNDEEP
cbit
Kyle
Kyle

Reputation: 103

Sign extending to 32 bits, starting with n bits - C

I am new to C and getting some practice with bit manipulation.

Suppose I have an n bit two's complement number such that n > 0 and n < 31. If I know the size of n in advance, how can I sign extend it to 32 bits?

If n was 16 bits,

int32_t extendMe(int16_t n) {
    return (int32_t) n;
}

assuming I have the data definitions.

Suppose I have an n bit value that I want to sign extend to 32, how can I accomplish this?

Thank you.

Upvotes: 1

Views: 1127

Answers (3)

royaltm
royaltm

Reputation: 430

5 years and only branching examples are in the answers? Ok, here we go:

#include "stdint.h"
#include "assert.h"

/** Convert a bit pattern as n-bit two's complement number up to 32 bits */
int32_t sgnext32(uint32_t pattern, int nbits)
{
    assert(nbits > 0 && nbits <= 32);
    uint32_t sgnbit = 1L << (nbits - 1);
    uint32_t lsmask = sgnbit | (sgnbit - 1);
    return (int32_t)((pattern + sgnbit) & lsmask) - sgnbit;
}

What we do here is we bring two's complement pattern from its <MIN_INT, MAX_INT> range to <0, MAX_UINT> range by adding abs(MIN_INT) (sgnbit), then we clip it to only n-bits (lsmask) and restoring the two's complement content, but in 32-bit space. This works for nbits = 32 too, because in this instance 32-bit overflow works exactly like the mask we apply.

int main()
{
    assert((int32_t) 0 == sgnext32(0, 1));
    assert((int32_t) -1 == sgnext32(1, 1));

    assert((int32_t) 0 == sgnext32(0, 2));
    assert((int32_t) 1 == sgnext32(1, 2));
    assert((int32_t) -1 == sgnext32(3, 2));
    assert((int32_t) -2 == sgnext32(2, 2));

    assert((int32_t) 0 == sgnext32(0, 15));
    assert((int32_t) 0x3fff == sgnext32(0x3fff, 15));
    assert((int32_t) -0x4000 == sgnext32(0x4000, 15));
    assert((int32_t) -1 == sgnext32(0x7fff, 15));
    assert((int32_t) -2 == sgnext32(0x7ffe, 15));

    assert((int32_t) 0 == sgnext32(0, 24));
    assert((int32_t) 0x7fffff == sgnext32(0x7fffff, 24));
    assert((int32_t) -0x800000 == sgnext32(0x800000, 24));
    assert((int32_t) -1 == sgnext32(0xffffff, 24));
    assert((int32_t) -2 == sgnext32(0xfffffe, 24));

    assert((int32_t) 0 == sgnext32(0, 32));
    assert((int32_t) 0x7fffffff == sgnext32(0x7fffffff, 32));
    assert((int32_t) -0x80000000 == sgnext32(0x80000000, 32));
    assert((int32_t) -1 == sgnext32(0xffffffff, 32));
    assert((int32_t) -2 == sgnext32(0xfffffffe, 32));
    return 0;
}

Looking back I'm pretty embarrassed by my original implementation of the algorithm, which in fact can be simplified to:

int32_t sgnext32(uint32_t pattern, int nbits)
{
    assert(nbits > 0 && nbits <= 32);
    nbits = 32 - nbits;
    return ((int32_t)(pattern << nbits) >> nbits);
}

Fun fact: the idea for the optimized version was revealed to me by the LLVM output assembly of the same algorithm I implemented in Rust.

Upvotes: 1

JeremyP
JeremyP

Reputation: 86651

An n-bit 2's complement number is negative if bit n - 1 is 1. In that case you want to fill all the bits from n to 31 with 1's. If it's zero, for completeness, you might also want to fill the bits from n to 31 with 0. So you need a mask, that you can use with bit operations to accomplish the above. This is easy to make. Assuming your n bit 2's complement number is held in a uint32_t:

int32_t signExtend(uint32_t number, int n)
{
    uint32_t ret;
    uint32_t mask = 0xffffffff << n;
    if (number & (1 << (n - 1)) != 0)
    {
        // number is negative
        ret = number | mask;
    }
    else 
    {
        // number is positive
        ret = number & ~mask;
    }
    return (int32_t) ret;
}

Completely untested and the last line might be UB but it should work on most implementations.

Upvotes: 1

user2371524
user2371524

Reputation:

If this really is about interpreting arbitrary bit patterns as numbers represented in n bits using two's complement, here's some sloppy example code doing that:

#include <stdio.h>
#include <inttypes.h>

// this assumes the number is in the least significant `bits`, with
// the most significat of these being the sign bit.
int32_t fromTwosComplement(uint32_t pattern, unsigned int bits)
{
    // read sign bit
    int negative = !!(pattern & (1U << (bits-1)));

    // bit mask for all bits *except* the sign bit
    uint32_t mask = (1U << (bits-1)) - 1;

    // extract value without sign
    uint32_t val = pattern & mask;

    if (negative)
    {
        // if negative, apply two's complement
        val ^= mask;
        ++val;
        return -val;
    }
    else
    {
        return val;
    }
}

int main(void)
{
    printf("%" PRId32 "\n", fromTwosComplement(0x1f, 5)); // output -1
    printf("%" PRId32 "\n", fromTwosComplement(0x01, 5)); // output 1
}

Upvotes: 2

Related Questions