I am trying solve the problem posed in this question that asks << 1 operation be performed on a 64 bit number using NAND operation only and without using any arithmetic operation. My attempted solution went as follows :
First I took an 8 bit number, scanned the digits by ANDing with powers of 2s, then shifted the digits leftward by ORring.
#include <stdio.h>
#define BIT 8
int main ()
{
unsigned char number = 121, shift = 0, digit;
unsigned char power[] = {1, 2, 4, 8, 16, 32, 64, 128, 0};
for (int i = 0; i < BIT+1; i++)
{
digit = power[i] & number;
if (number & digit != 0) {shift = shift | power[i+1];}
}
printf ("8bit number = %u\nnumber << 1 = %u", number, shift);
return 0;
}
Once it worked I replaced the AND, OR, NOT logic with NAND logic by using the following identities derived by applying Demorgan.
NAND (x, y) = OR (NOT(x), NOT(y))
AND (x, y) = NAND (NAND (x, y), NAND (x, y))
OR (x, y) = NAND (NAND (x, x), NAND (y, y))
Also enabled user input and made sure that it shows that the result of our custom shifter equals the result of the built in shifter.
#include <stdio.h>
#define BIT 8
unsigned char NAND (unsigned char x, unsigned char y)
{
return ~x | ~y;
}
void bitwise_shift (unsigned char * input, unsigned char * output)
{
*output = *input << 1;
}
void nand_shift (unsigned char * input, unsigned char * output)
{
unsigned char digit, power[] = {1, 2, 4, 8, 16, 32, 64, 128, 0};
*output = 0;
for (int i = 0; i < BIT+1; i++)
{
digit = NAND (NAND (*input, power[i]), NAND (*input, power[i]));
if (NAND (NAND (*input, digit), NAND (*input, digit)) != 0)
{
*output = NAND (NAND (*output, *output), NAND (power[i+1], power[i+1]));
}
}
}
int main ()
{
while (1)
{
unsigned char number, nand_shifted, bitwise_shifted;
printf ("Give me an 8-bit number x = ");
int temp = scanf ("%u", &number);
if (temp != 1 | temp == EOF) {break;}
nand_shift (&number, &nand_shifted);
bitwise_shift (&number, &bitwise_shifted);
printf ("x << 1 = %u\nx x << 1 (NAND) = %u\n\n", bitwise_shifted, nand_shifted);
}
printf ("!!ERROR!!");
return 0;
}
Once it worked I attempted to extend it to 64-bit. I changed all the unsigned char types to unsigned long long types and calculated the powers of 2's array (now containing 65 element) by running this side programme and copy pasting its output into the main program.
#include <stdio.h>
#define BIT 64
void generate_power_array ()
{
int base = 2, exponent = BIT-1;
unsigned long long power = 1;
printf ("power[] = {1");
for (int i = 1; i <= exponent; i++)
{
power *= base;
printf (", %llu", power);
}
printf (", 0};");
}
int main ()
{
generate_power_array ();
}
I ended up with the following which works but gives this- "warning: integer constant is so large that it is unsigned".
#include <stdio.h>
#define BIT 64
unsigned long long NAND (unsigned long long x, unsigned long long y)
{
return ~x | ~y;
}
void bitwise_shift (unsigned long long * input, unsigned long long * output)
{
*output = *input << 1;
}
void nand_shift (unsigned long long * input, unsigned long long * output)
{
unsigned long long power[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944, 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624, 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976, 2305843009213693952, 4611686018427387904, 9223372036854775808, 0};
unsigned long long digit;
*output = 0;
for (int i = 0; i < BIT+1; i++)
{
digit = NAND (NAND (*input, power[i]), NAND (*input, power[i]));
if (NAND (NAND (*input, digit), NAND (*input, digit)) != 0)
{
*output = NAND (NAND (*output, *output), NAND (power[i+1], power[i+1]));
}
}
}
int main ()
{
while (1)
{
unsigned long long number, nand_shifted, bitwise_shifted;
printf ("Give me a 64-bit number x = ");
int temp = scanf ("%llu", &number);
if (temp != 1 | temp == EOF) {break;}
nand_shift (&number, &nand_shifted);
bitwise_shift (&number, &bitwise_shifted);
printf ("x << 1 = %llu\nx << 1 (NAND) = %llu\n\n", bitwise_shifted, nand_shifted);
}
printf ("!!ERROR!!");
return 0;
}
But if I do the same for 32-bit numbers, by changing all the unsigned char types to unsigned int types and by calculating the powers of 2s array using the aforementioned side programme, I get the following, which works fine and gives no warning.
#include <stdio.h>
#define BIT 32
unsigned int NAND (unsigned int x, unsigned int y)
{
return ~x | ~y;
}
void bitwise_shift (unsigned int * input, unsigned int * output)
{
*output = *input << 1;
}
void nand_shift (unsigned int * input, unsigned int * output)
{
unsigned int power[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304, 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 0};
unsigned int digit;
*output = 0;
for (int i = 0; i < BIT+1; i++)
{
digit = NAND (NAND (*input, power[i]), NAND (*input, power[i]));
if (NAND (NAND (*input, digit), NAND (*input, digit)) != 0)
{
*output = NAND (NAND (*output, *output), NAND (power[i+1], power[i+1]));
}
}
}
int main ()
{
while (1)
{
unsigned int number, nand_shifted, bitwise_shifted;
printf ("Give me an 8-bit number x = ");
int temp = scanf ("%u", &number);
if (temp != 1 | temp == EOF) {break;}
nand_shift (&number, &nand_shifted);
bitwise_shift (&number, &bitwise_shifted);
printf ("x << 1 = %u\nx x << 1 (NAND) = %u\n\n", bitwise_shifted, nand_shifted);
}
printf ("!!ERROR!!");
return 0;
}
So, I have one solution for 3 situations. For 8-bit it works, for 32-bit it works, for 64-bit it works but gives this- "warning: integer constant is so large that it is unsigned". Where is this warning originating from and how can it be gotten rid of?
A decimal integer constant without any suffix is always considered a signed type.
As the number 9223372036854775808 is greater than the largest 64-bit signed integer, the compiler cannot determine a type in accordance with the C standard.
It seems your compiler instead decides to assign it an unsigned type and gives you a warning that something non-standard is going on.
By adding the suffix u like 9223372036854775808u the warning goes away as the type is now unsigned per standard.
In your case I would recommend using hex values instead, like 0x8000000000000000. Hex integer constants automatically get an unsigned type if they are greater than the maximum signed value for a given width and your program will be easier to read and understand.