Как вернуть 1, если x * x может уместиться в 32-разрядное целое число, и 0 в противном случае?

Question

Я работаю над вопросом и должен написать метод, который возвращает 1, если x * x может уместиться в 32-разрядное целое число, и 0 в противном случае.
Я подумал, что смогу проверить, больше ли число, чем 46340 (квадратный корень из наибольшего числа, которое может быть представлено с помощью двоичного представления дополнения 2). Однако я не могу, потому что я ограничен в использовании до 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 */
}

Хорошо, после прочтения комментариев я решил добавить ограничения: используйте ТОЛЬКО следующее:

• Целочисленные константы от 0 до 255 (0xFF) включительно.Вы не можете использовать большие константы, такие как 0xffffffff.
• Аргументы функции и локальные переменные (без глобальных переменных).
• Унарные целочисленные операции!~
• Двоичные целочисленные операции & ^ |+ << >>

Answer 1

Вы хотите реализовать abs(x) < 46341 (или 0xb505) с некоторыми глупыми ограничениями.

Этот вопрос кажется довольно сложным для 32-битного int со знаком и еще сложнее для простого int.

Если вопрос был неверно сформулирован и относится к 32-битным беззнаковым целым, вот решение:

 /*
  * 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);
}

Если вопрос действительно относится к 32-битной знаковой int с дополнением до двухТаким образом, вы можете убедиться, что это работает для всех значений:

#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;
}

Объяснение:

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)

Проверка знакового бита путем преобразования в unsigned и сдвига вправо на 31 позицию.Преобразование в unsigned подразумевает, что один из операндов не подписан, поэтому x + 0U преобразует x в тип без знака.Аналогичный трюк используется для других выражений.

Answer 2

Ответ подразумевает неподписанное, измените для вашей конкретной домашней работы

Если какой-либо из битов установлен в третьем или четвертом байте, то вы не можете его подогнать, поэтому ваш учитель хочет что-то вроде:

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

Если установлены какие-либо биты в этих байтах, вы не можете вписать квадрат в 32-битное целое число.Если бы вопрос был о unsigned int 32, это был бы конец, но с битом знака вы должны также выполнить некоторую проверку второго байта, поскольку 0xFFFF * 0xFFFF больше, чем max со знаком int.

Поскольку выникогда не может действительно иметь отрицательный квадрат, вариант без знака должен быть альтернативным ответом, но я не написал это назначение.

РЕДАКТИРОВАТЬ (если битовый паттерн уникален, вы должны замаскировать...)

#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
}

Вывод:

-46341 подходит, а -46342 не

46341 не подходит, а 46340

Я чувствую, что просто потратил час своей жизни, выполняя эту домашнюю работу, ребята ...

Answer 3

Эта проблема неопределенно определена, и я думаю, что вы ее истолковали так, что вам стало труднее, чем нужно.

Если вы интерпретируете «вписать в 32-битное целое число»как беззнаковое 32-разрядное целое число, квадратный корень максимального значения (2 ³² ) имеет гораздо более удобное значение (2 ¹⁶ ).Я почти уверен, что это то, что было задумано.

Answer 4

Согласно комментарию к коду, << и | разрешены, так что вы можете просто создать большую константу, используя shift и или .... Это проще при преобразовании числа в шестнадцатеричное:

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

Это не полностью решает проблему, так как у вас нет доступных сравнений (это ограничение было добавлено позже).

В этом случае я ожидаю, что эта проблема будетцелые числа без знака.Здесь вам просто нужно проверить, установлен ли какой-либо из 16 старших битов.К счастью, ! находится в списке разрешенных операций, поэтому вы можете просто применить не к числу, сдвинутому вправо на 16.

Если проблема на самом деле для чисел со знаком, то это более сложно.Вы можете использовать - и проверить бит знака для замены оператора сравнения:

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

Чтобы быть более безопасными, вы можете применить двойное не (!!) для защиты от специфичного для реализации поведениясдвиг вправо со знаковыми номерами.