Sign extending bit shifted binary values in C++ using only bitwise operators

Question

I have written the following function which is meant to extract bits 5 through 8 (inclusive) of an integer and return those bits. However, the extracted bits are treated as signed so therefore they must be sign extended after bit shifting.

int signedBits5through8(int v){
  int fourBits = (v & 0b111111111) >> 5;
  int signBit = (fourBits & 0b1000) >> 3;
  return (0b11111111111111111111111111110000 * signBit) | fourBits;
}

In order to achieve sign extension, my implementation multiplies the sign bit (the most significant bit of the extracted 4 bits, following twos complement conventions) by 28 bits of 1s followed by 4 bits of zeros in order to "sign extend", and then uses an OR mask to apply the last 4 bits. My issue is that I am unable to use any operators other than bitwise ones for this task, and so using the multiplication operator is unacceptable. What's the best work-around in this situation? I also cannot use any conditional or loop logic (if-else, for, etc) in my function.

Answer 1

As @user207421 suggested in the comments, you can sign-extend by bit-shifting without using the sign bit explicitly.

Note that before c++20 when two's complement representation was not yet required by the standard, this was considered conditionally UB (even though MSVC seems not to think so, which is probably a compiler bug) if the left shift causes signed overflow.

As code, the suggestion looks like this:

int signedBits5through8(int v) {
  return (v << 23) >> 28;
}

Here are some tests to show it works as intended in all the major compilers, using constant evaluation to ensure that no UB is evaluated (at least with c++20 standard enabled): https://godbolt.org/z/6aonbxsbs

constexpr int signedBits5through8(int v) {
  return (v << 23) >> 28;
}

static_assert(signedBits5through8(0b11111111111111111111111'0000'11111) == +0b0000);
static_assert(signedBits5through8(0b11111111111111111111111'0001'11111) == +0b0001);
static_assert(signedBits5through8(0b11111111111111111111111'0010'11111) == +0b0010);
static_assert(signedBits5through8(0b11111111111111111111111'0011'11111) == +0b0011);
static_assert(signedBits5through8(0b11111111111111111111111'0100'11111) == +0b0100);
static_assert(signedBits5through8(0b11111111111111111111111'0101'11111) == +0b0101);
static_assert(signedBits5through8(0b11111111111111111111111'0110'11111) == +0b0110);
static_assert(signedBits5through8(0b11111111111111111111111'0111'11111) == +0b0111);
static_assert(signedBits5through8(0b11111111111111111111111'1000'11111) == -0b1000);
static_assert(signedBits5through8(0b11111111111111111111111'1001'11111) == -0b0111);
static_assert(signedBits5through8(0b11111111111111111111111'1010'11111) == -0b0110);
static_assert(signedBits5through8(0b11111111111111111111111'1011'11111) == -0b0101);
static_assert(signedBits5through8(0b11111111111111111111111'1100'11111) == -0b0100);
static_assert(signedBits5through8(0b11111111111111111111111'1101'11111) == -0b0011);
static_assert(signedBits5through8(0b11111111111111111111111'1110'11111) == -0b0010);
static_assert(signedBits5through8(0b11111111111111111111111'1111'11111) == -0b0001);

Answer 2

The canonical way of sign-extending under the classical limitations on shifting of signed operands is to flip the sign bit using XOR, then flip it back using subtraction. The latter will cause the desired carry propagation to more significant bits.

#include <cstdio>
#include <cstdlib>

int signedBits5through8 (int v)
{
    const unsigned int all_bits = 0xf;
    const unsigned int sign_bit = 0x8;
    unsigned int uv = (unsigned int)v;
    unsigned int bits = (uv >> 3) & all_bits;
    return (int)((bits ^ sign_bit) - sign_bit);
}

int main (void)
{
    for (int i = 0; i < 128; i++) {
        printf ("%3d %3d\n", i, signedBits5through8 (i));
    }
    return EXIT_SUCCESS;
}

If subtraction is disallowed, that would need to be replaced with emulation, for example:

int add (int x, int y) 
{
    unsigned int sum, carry;
    carry = x & y;
    sum = x ^ y;
    while (carry) {
        x = carry << 1; // weight of carry bits is twice weight of sum bits
        y = sum;
        carry = x & y;
        sum = x ^ y;
    };
    return (int)sum;
}

int sub (int x, int y)
{
    return add (add (x, ~y), 1);
}