3

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 :

  1. 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;
 }

  2. 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;
}

  1. 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?

Improve this question
4
  • 1
    2147483648 is too large for an int. You can make it unsigned with a u suffix. 2147483648u. Commented Aug 3 at 6:01
  • @BoP The problem comes from 9223372036854775808, not 2147483648 Commented Aug 3 at 7:08
  • @BoP Tested it. It works. Thank you. Commented Aug 3 at 7:15
  • OT: Why did you implement NAND as OR with inverted inputs? Sure, by De Morgan's law it is equivalent. But as your tutor I would cut you points for this, as return ~(x & y) would be the "correct" implementation. Commented Aug 3 at 10:08

2 Answers 2

Reset to default
4

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.

Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

I took the liberty to amend your answer for correctness. The type of hex, octal and binary constants is not always unsigned, only if their value is specific ranges: INT_MAX+1 .. UINT_MAX, LONG_MAX+1 .. ULONG_MAX and LLONG_MAX+1 .. ULLONG_MAX.
Thanks for updating. My wording was insufficient.
I would use a hex constant because it makes the significance of the value clearer, and use a u suffix because it makes the signedness of the value's type clearer.
C23 allow a quote character in number constants. Useful to clearly see the zero count as in 0x8000000000000000 --> 0x8000'0000'0000'0000.
@chux: it was useful to introduce digit separators, but _ was the obvious and logical choice, that did not even require a change in the pp-number preprocessor token definition. The C++ option to use ' for this purpose is nonsensical.
2

Based on the feedback provided by other members it appears there are 2 ways to solve this problem. 1) use hexadecimal, which can be implemented by changing the last entry of the unsigned long long power[] array in the void nand_shift () function from decimal 9223372036854775808 to hexadecimal 0x8000000000000000, so that the programme looks like this :

  #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, 0x8000000000000000, 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;
  }

An alternative option 2) is to use the suffix u after every number in the power[] array so that it becomes explicitly stated that these numbers are unsigned. This solution can be implemented in the following way :

  1. Rewrite the generate_power_array () function in a manner such that all numbers have a u suffix attached to them, explicitly stating to the compiler that these numbers are unsigned.

    #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 ("u, %llu", power);
    }
    printf ("u, 0u};");
}

int main ()
{
    generate_power_array ();
}

  2. Copy paste the output of the generate_power_array () function to initialize the unsigned long long power[] array in the void nand_shift () function. The rest of the programme remains unchanged.

    #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[] = {1u, 2u, 4u, 8u, 16u, 32u, 64u, 128u, 256u, 512u, 1024u, 2048u, 4096u, 8192u, 16384u, 32768u, 65536u, 131072u, 262144u, 524288u, 1048576u, 2097152u, 4194304u, 8388608u, 16777216u, 33554432u, 67108864u, 134217728u, 268435456u, 536870912u, 1073741824u, 2147483648u, 4294967296u, 8589934592u, 17179869184u, 34359738368u, 68719476736u, 137438953472u, 274877906944u, 549755813888u, 1099511627776u, 2199023255552u, 4398046511104u, 8796093022208u, 17592186044416u, 35184372088832u, 70368744177664u, 140737488355328u, 281474976710656u, 562949953421312u, 1125899906842624u, 2251799813685248u, 4503599627370496u, 9007199254740992u, 18014398509481984u, 36028797018963968u, 72057594037927936u, 144115188075855872u, 288230376151711744u, 576460752303423488u, 1152921504606846976u, 2305843009213693952u, 4611686018427387904u, 9223372036854775808u, 0u};
    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;
}

In these ways there will be no error &/ warnings.

Improve this answer

5 Comments

The usage of hex is shown in this answer. Please be aware that we are talking about textual representation of values in source code here. The CPU handles all values in binary.
Yes tested it, it works, will edit the answer. Thanks.
I would express all the initializers for the power array in hexadecimal form. It's easier to do correctly, and much clearer for anyone verifying or just reading the code. I would also give them all u suffixes for clarity, even though that's not strictly necessary for correct semantics in this case.
Note: if (temp != 1 | temp == EOF) {break;} same as if (temp != 1) {break;}
Given unsigned long long is at least 64-bit, consider using uint64_t to work with "Give me a 64-bit number x = ". A bit of future proofing as I suspect issues with NAND() should code get compiled on a wider than 64-bit unsigned long long.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.