How to return 1 if x*x can fit in a 32-bit integer, and 0 otherwise?

▲
-2
▼

I am working on a question and I am supposed to write a method that returns 1 if x*x can fit in a 32-bit integer, and 0 otherwise.
I thought that I could check if the number is larger than 46340 ( square root of the largest number that can be represented using 2's complement binary representation.) However I can't because I am limited to use upmost 255. 

 /*
 * squaredOK - Return 1 if x*x can 
fit 
 in 
 a 32-bit integer, and 0 otherwise.
  *  Examples: squaredOK(10) = 1
 *            squaredOK(1000000) = 0
 *  Legal ops: ! ~ & ^ | + - << >>
 *  Max ops: 20
 */
int squaredOK(int x) {

return ; /* no idea */
}

Okay after reading the comments I decided to add the limitations: use ONLY the following:

  • Integer constants 0 through 255 (0xFF), inclusive. You are not allowed to use big constants such as 0xffffffff.
  • Function arguments and local variables (no global variables).
  • Unary integer operations ! ~
  • Binary integer operations & ^ | + << >>
c
binary
bit-manipulation
bitwise-operators
asked on Stack Overflow Oct 12, 2018 by S_F_S • edited Oct 12, 2018 by Kevin

4 Answers

▲
0
▼

According to the code comment, << and | are allowed, so you could just produce a bigger constant using shift and or.... This is simpler when converting the number to hex:

 46340 == 0xb504 == (0xB5 << 8) | 0x04

This doesn't fully solve the problem, as you don't seem to have comparison available (this restriction was added later).

In this case, I'd expect this problem to be for unsigned integers. Here, you just need to check if any of the 16 high bits is set. Fortunately, ! is in the list of permitted operations, so you can just apply not to the number shifted to the right by 16.

If the problem is actually for signed numbers, it's more tricky. You could use - and a check for the sign bit to replace the comparison operator:

int squaredOK(int x) {
   return (x - ((0xB5 << 8) | 4)) >> 31 
}

To be extra safe, you could apply a double not (!!) to guard against implementation specific behavior of right shift with signed numbers.

answered on Stack Overflow Oct 12, 2018 by Stefan Haustein • edited Oct 12, 2018 by Eric Postpischil
▲
0
▼

This problem is vaguely defined, and I think you've interpreted it in a way that's making it harder for yourself than it needs to be.

If you interpret "fit in a 32-bit integer" as an unsigned 32-bit integer, the square root of the maximum value (232) has a much more convenient value (216). I'm pretty certain this is what was intended.

answered on Stack Overflow Oct 12, 2018 by duskwuff -inactive-
▲
0
▼

You want to implement abs(x) < 46341 (or 0xb505) with some silly limitations.

This question seems quite difficult for signed 32-bit int, and even harder for plain int.

If the question was misformulated and applies to 32-bit unsigned ints, here is a solution:

 /*
  * squaredOK - Return 1 if x*x can fit in a 32-bit integer, and 0 otherwise.
  *  Examples: squaredOK(10) = 1
  *            squaredOK(1000000) = 0
  *  Legal ops: ! ~ & ^ | + - << >>
  *  Max ops: 20
  */
int squaredOK(uint32_t x) {
    return !(x >> 16);
}

If the question really applies to 32-bit signed int with two's complement representation, you can verify that this works for all values:

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

int squaredOK(int32_t x) {
    return !(x + 0U >> 31) & x - (0xB5 << 8 | 5U) >> 31 |
           x + 0U >> 31 & !(x + (0xB5 << 8 | 4U) >> 31);
}

int main() {
    long long x;
    for (x = INT32_MIN; x <= INT32_MAX; x++) {
        if (squaredOK(x) != (x * x <= INT32_MAX)) {
            printf("failed on %lld\n", x);
            return 1;
        }
    }
    return 0;
}

Explanation:

x < 46341 && x > -46341
(x >= 0 && x < 46341) || (x < 0 && x > -46341)
(x >= 0 && x - 46341 < 0) || (x < 0 && x + 46340 >= 0)
(x >= 0 && x - (0xB5<<8|5) < 0) | (x < 0 && x + (0xB5<<8|4) >= 0)
(!(x+0U>>31) & (x - (0xB5<<8|5U)) >> 31) | ((x+0U>>31) & !((x + (0xB5<<8|4U)) >> 31)

Testing the sign bit by converting to unsigned and shifting right 31 places. Conversion to unsigned is implicit of one of the operands is unsigned, hence x + 0U converts x to an unsigned type. A similar trick is used for the other expressions.

answered on Stack Overflow Oct 12, 2018 by chqrlie • edited Oct 12, 2018 by chqrlie
▲
-1
▼

Answer assumes unsigned, modify for your specific homework

If any of the bits are set on the third or forth byte then you cant fit it, so your teacher wants something like:

          //check the third byte for bits      //check the 4th byte for bits
retbool = (((unsigned char)(x >> 16) & 0xFF) | ((unsigned char)(x >> 24) & 0xFF)));

If any bits in those bytes are set then you can not fit the square in the 32 bit int. If the question was about unsigned int 32 this would be the end, but with the sign bit you have to do some checking on the second byte as well since 0xFFFF * 0xFFFF is more than max signed int.

Since you can never really have a negative square the unsigned version should be an alternative answer, but i didnt write this assignment.

EDIT (if the bit patter is unique you have to mask...)

#include <stdio.h>

int doesFit(int x);

typedef unsigned char uchar;
typedef unsigned short ushort;

#define MAX_POS_SQUARE 46340
#define MAX_NEG_SQUARE -46340

int main(void) {
    int x=MAX_NEG_SQUARE -2;
    int fits = -1;
    int prevoiusly_fit = 0;
    for(;x<MAX_POS_SQUARE+5;x++){
        fits = doesFit(x);
        if(!fits && prevoiusly_fit){
            printf("%d didnt fit and %d did\n",x,x-1);
        }
        else if(fits && !prevoiusly_fit){
            printf("%d fit and %d did not\n",x,x-1);
        }
        prevoiusly_fit = fits;
    }
    return 0;
}

int doesFit(int x){
    uchar bits_left = 16;
    ushort pos_mask = ((0xb5 << 8) | 0x04);
    ushort neg_mask = ((0xb5 << 8) | 0x05);
    ushort x_16_low = (((-x) & 0xff << 8 ) | (-x) & 0xff); //used in negative case
    ushort x_16_high = (-x)>>16; //used in negative case
    //Handle the negative case
    //printf("0x%04x x: 0x%04x x_16_low: 0x%04x x_16_high:", x, x_16_low, x_16_high);
    if(x>>31){
    //how can you tell if a value x < -46340
        if( (x_16_high & 0xFF) | (x_16_high >>8 & 0xFF)){
            //doesnt fit, maybe dont use compliment use ! if accidental promotion occurs
            printf("bailing out when x=%d\n", x);
            return 0;
        }
        while(bits_left){
            --bits_left;
            if(x_16_low & (1 << bits_left)){
                if(!(neg_mask & (1 << bits_left))){
                    return 0;
                }
            } 
            else if(!(x_16_low & (1 << bits_left))){
                if(neg_mask & (1 << bits_left)){
                    return 1;
                }
            }
            //high bits matched with max value bits, cant tell yet, keep masking.
        }
    }
    else{ //handle the positive case
        //how can you tell if a value x > 46340
        if( (x >> 16 & 0xFF) | (x >>24 & 0x7F)){
            //doesnt fit, return false
            return 0;
        }
        while(bits_left){
            --bits_left;
            if(x & (1 << bits_left)){
                if(!(pos_mask & (1 << bits_left))){
                    return 0;
                }
            } 
            else if(!(x & (1 << bits_left))){
                if(pos_mask & (1 << bits_left)){
                    return 1;
                }
            }
            //high bits matched with max value bits, cant tell yet, keep masking.
        }
    }
    return 1; //Must be the exact size to fit to get to this return
}

Output:

-46341 fit and -46342 did not

46341 didnt fit and 46340 did

I feel like i just wasted an hour of my life doing this guys homework...

answered on Stack Overflow Oct 12, 2018 by Bwebb • edited Oct 12, 2018 by Bwebb

User contributions licensed under CC BY-SA 3.0