Twiddling bit in C - computes 2 times x or returns the largest signed number

Question

I am writing a function that calculates the x parameter 2 times, but if it overflows, it should return the largest positive or negative signed number. The problem is that I can only use ! ~ & ^ | + << >> ! ~ & ^ | + << >> ! ~ & ^ | + << >> . 32-bit integers are used.

This is what I still have:

 int boundedMult(int x){ int xSign = x>>31 int y = x << 1; // Multiply by 2 int signBit = y>>31; // Capture the signBit of the answer int shift = signBit; shift |= shift<<1; // Make shift all 1 or 0 depending on the sign bit shift |= shift<<2; shift |= shift<<4; shift |= shift<<8; shift |= shift<<15; int answer = ~signBit<<31 | shift; // 01111... If signBit=1 and 1000... If signBit=0 } 

Seems good, right? I also cannot use any constants outside the unsigned byte (0-255) inclusive . I tried so many approaches, but in the end I broke one of these rules in all of them.

Answer 1

An interesting challenge! Here is my solution, I hope that I did not violate any restrictions by mistake:

 #include <stdio.h> #include <stdint.h> // work with uint to avoid undefined behavior (signed int overflow is undefined) static inline int32_t x2(int32_t v) { uint32_t uv = v; // our first option: "multiply" by shifting: uint32_t doubled = uv<<1; // our second option: clamp to max/min integer: uint32_t neg = !!(uv >> 31); // 1 if negative uint32_t bigval = (~0u)>>1; // 0x7fffffff uint32_t clamped = bigval + neg; // 0x80000000 if neg, 0x7fffffff otherwise // so, which one will we use? uint32_t ok = !((v>>31) ^ (v>>30)); // 0 if overflow, 1 otherwise // note the use of signed value here uint32_t mask = (~ok)+1; // 0x00000000 if overflow, 0xffffffff otherwise // choose by masking one option with ones, the other with zeroes return (mask & doubled) | ((~mask) & clamped); } static inline void check(int32_t val, int32_t expect) { int32_t actual = x2(val); if ((val & 0x3ffffff) == 0) { printf("0x%08x...\n", val); } if (actual != expect) { printf("val=%d, expected=%d, actual=%d\n", val, expect, actual); } } int main() { int32_t v = 0x80000000; printf("checking negative clamp...\n"); for (; v < -0x40000000; ++v) { check(v, 0x80000000); } printf("checking straight double...\n"); for(; v < 0x40000000; ++v) { check(v, 2*v); } printf("checking positive clamp...\n"); for(; v < 0x7fffffff; ++v) { check(v, 0x7fffffff); } check(0x7fffffff, 0x7fffffff); printf("All done!\n"); return 0; } 

And it works fine:

 gcc -std=c99 -O2 -Wall -Werror -Wextra -pedantic bounded.c -o bounded && ./bounded checking negative clamp... 0x80000000... 0x84000000... 0x88000000... 0x8c000000... 0x90000000... 0x94000000... 0x98000000... 0x9c000000... 0xa0000000... 0xa4000000... 0xa8000000... 0xac000000... 0xb0000000... 0xb4000000... 0xb8000000... 0xbc000000... checking straight double... 0xc0000000... 0xc4000000... 0xc8000000... 0xcc000000... 0xd0000000... 0xd4000000... 0xd8000000... 0xdc000000... 0xe0000000... 0xe4000000... 0xe8000000... 0xec000000... 0xf0000000... 0xf4000000... 0xf8000000... 0xfc000000... 0x00000000... 0x04000000... 0x08000000... 0x0c000000... 0x10000000... 0x14000000... 0x18000000... 0x1c000000... 0x20000000... 0x24000000... 0x28000000... 0x2c000000... 0x30000000... 0x34000000... 0x38000000... 0x3c000000... checking positive clamp... 0x40000000... 0x44000000... 0x48000000... 0x4c000000... 0x50000000... 0x54000000... 0x58000000... 0x5c000000... 0x60000000... 0x64000000... 0x68000000... 0x6c000000... 0x70000000... 0x74000000... 0x78000000... 0x7c000000... All done! 

Using this convenient interactive compiler , we can get disassembly for different platforms. Annotated ARM64 build:

 x2(int): asr w1, w0, 30 # w1 = v >> 30 cmp w1, w0, asr 31 # compare w1 to (v>>31) csetm w1, eq # w1 = eq ? 0 : -1 # --- so w1 is "mask" mov w2, 2147483647 # w2 = 0x7fffffff mvn w3, w1 # w3 = ~w1 # --- so w3 is ~mask add w2, w2, w0, lsr 31 # w2 = w2 + (v>>31) # --- so w2 is "clamped" and w2, w3, w2 # w2 = w3 & w2 and w0, w1, w0, lsl 1 # w0 = w1 & (v << 1) orr w0, w2, w0 # w0 = w2 | w0 ret # return w0 

It looks pretty effective for me. It's pretty sweet that a "doubling" is never stored in the register - it is simply done as a shift in the input value for one of the commands and commands.

Answer 2

Like this?

 int boundedMult(int x) { int xSign = (x >> 31) & 1; int resultArray[] = {x + x, x + x, ~(1 << 31), 1 << 31}; int willOverflow = xSign ^ ((x >> 30) & 1); return resultArray[(willOverflow << 1) + xSign]; } 

Just as @Tom Karzes wisely pointed out in a comment: "To see if the result will overflow, all you have to do is see if the two high-order bits are different in the original number."

Answer 3

This can be done without knowing how many bits there are in the int. Overflow means the sign bit changes if you are * 2, then / 2. The change can be detected via xor and ends with min int in 2 additions.

 int t2(int v) { int v2=v<<1; // *2 int ovfl=(v2>>1)^v; // smallest negative # if overflow or 0 if not return (ovfl&v)+(~ovfl&~!!(ovfl&~v)+1)+((~!ovfl+1)&v2); } 

or

 template<class T> T t2(T v) { T v2=v<<1; // *2 T ovfl=(v2>>1)^v; // smallest negative # if overflow or 0 if not return (ovfl&v)+(~ovfl&~!!(ovfl&~v)+1)+((~!ovfl+1)&v2); } 

Answer 4

Here is one approach, this is not the best approach, and it can be optimized, but this approach is easily explained. Optimization is quite simple.

 int boundedMult(int x){ int ans = x << 1; // if the sign bit between ans and x is different an overflow occured int ansSign = (ans >> 31) & 1; int xSign = (x >> 31) & 1; // but we can't use branching, so instead let construct a number int overflowed = ansSign ^ xSign; // let shift this up to the signbit overflowed <<= 31; // And let subtract 1 to make it INTMAX or -1, we're doing this because -1 // is all 1s, so we can OR this later on. overflowed += ~1+1; // now overflowed contains INTMAX if an overflow has occured and -1 otherwise // but we want -INTMAX if x is negative, we do this by taking the complement of // overflowed if xSign is set. A way to take the complement is to xor by // -1. How can we make a negative 1? // Four possibilities for xSign and ansSign at this point: // ansSign xSign Meaning // 0 0 x positive no overflow // 1 0 x positive overflow // 1 1 x negative no overflow // 0 1 x negative overflow // We want to detect the case "x negative overflow" without detecting any // other case, and we want to generate a negative 1, generating a 0 for all // other cases. // ansSign xSign -(!ansSign & xSign) // 0 0 0 // 1 0 0 // 1 1 0 // 0 1 -1 overflowed ^= ~(!ansSign & xSign) + 1; // Now overflowed contains INTMAX, -INTMAX or 0 as appropriate, so let's // rename it int aproposMaxIfOverflowed = overflowed; // But there one other problem. We only want to overwrite ans if an // overflow happened So because -(ansSign ^ xSign) is either all 1s if an // overflow occured or all zeros if it hasn't we can use it to blank or keep // numbers // This contains all 1s or ans int ansIfNotOverflowed = ans | (~(ansSign ^ xSign) + 1); // So now we have ansIfNotOverflowed, and aproposMaxIfOverflowed, we can // combine these now return ansIfNotOverflowed & aproposMaxIfOverflowed; }