Monthly Archives: November 2017

C/C++: Hack to use an array of 4 characters as one unsigned 32 bit integer and increment their value by one

 in C by

In this scenario, we had 4 unsigned char variables.
The first variable was counting ‘something’.
The second variable was counting how many times the first variable reached its maximum value and then overflowed.
The third variable was counting how many times the second variable reached its maximum value and then overflowed.
Finally, the fourth variable was counting how many times the third variable reached its maximum value and then overflowed.

What we wanted to achieve was to perform this process without using several if statements that check when each variable overflowed and then perform the corrective actions.
The trick that we did to achieve the expected result works on the principle that an array in C/C++ always holds consecutive memory spaces.

What we did was cast the array pointer as a pointer of an unsigned int variable, this allowed us to operate on all 4 bytes at the same time as if they were one.
We can do the same for an array composed of two unsigned short integers.
This trick can of course work on 64bit variables and arrays that contain 8 unsigned char elements or 4 unsigned short elements or 2 unsigned int elements.

++(*((unsigned int *)&t));

Full Example

[download id=”3883″]

#include <stdio.h>
#include <time.h>
#include <stdlib.h>

static inline void increment(unsigned char t[4]) {
  if (t[0] == 0xFF) {
    if (t[1] == 0xFF) {
      if (t[2] == 0xFF) {
        ++t[3];
      }
      ++t[2];
    }
    ++t[1];
  }
  ++t[0];
}

int main() {
  const unsigned int final_limit = (unsigned int) -1; //or 0xFFFFFFFF
  const unsigned int intermediate_limit = 0xABCDEF00;

  {
    unsigned char t[4] = {0, 0, 0, 0};
    printf("%02X %02X %02X %02X - Initial Values\n", t[3], t[2], t[1], t[0]);
    const clock_t start = clock();

    unsigned int i;
    for (i = 0; i < intermediate_limit; ++i) {
      ++(*((unsigned int *)&t));
    }

    printf("%02X %02X %02X %02X - Intermediate Values\n", t[3], t[2], t[1], t[0]);

    for (; i < final_limit; ++i) {
      ++(*((unsigned int *)&t));
    }

    const clock_t end = clock();
    const float seconds = (float) (end - start) / CLOCKS_PER_SEC;
    printf("%02X %02X %02X %02X - Final Values\n", t[3], t[2], t[1], t[0]);
    printf("Seconds elapsed %f\t by casting array of unsigned chars to an unsigned int\n", seconds);
  }

  {
    unsigned char t[4] = {0, 0, 0, 0};
    printf("%02X %02X %02X %02X - Initial Values\n", t[3], t[2], t[1], t[0]);
    const clock_t start = clock();

    unsigned int i;
    for (i = 0; i < intermediate_limit; ++i) {
      increment(t);
    }

    printf("%02X %02X %02X %02X - Intermediate Values\n", t[3], t[2], t[1], t[0]);

    for (; i < final_limit; ++i) {
      increment(t);
    }

    const clock_t end = clock();
    const float seconds = (float) (end - start) / CLOCKS_PER_SEC;
    printf("%02X %02X %02X %02X - Final Values\n", t[3], t[2], t[1], t[0]);
    printf("Seconds elapsed %f\t by using various if statements to control overflow\n", seconds);
  }

  return 0;
}

[download id=”3883″]

Output

00 00 00 00 - Initial Values
AB CD EF 00 - Intermediate Values
FF FF FF FF - Final Values
Seconds elapsed 7.938144 by casting array of unsigned chars to an unsigned int
00 00 00 00 - Initial Values
AB CD EF 00 - Intermediate Values
FF FF FF FF - Final Values
Seconds elapsed 12.820061 by using various if statements to control overflow

A peculiar way to get the biggest (max/maximum) value between two variables using bitwise operations 3

 in C  tagged bit / bitwise / C++ / clock / CLOCKS_PER_SEC / max / maximum / rand / srand / XOR by

Recently, we wanted to make a test and see how we could find the maximum value between two variables using bitwise operations.

We ended up with the following peculiar way to get the biggest value between two variables using bitwise operations


r = a ^ ((a ^ b) & -(a < b));

The above formula has two modes:

  1. When a < b
  2. When a >= b

 

When a < b then the formula will change as follows:


r = a ^ ((a ^ b) & 0xFFFFFFFF);

As we all (should) know, when one of the operators on a bitwise AND operation is composed only from 1s, then the result is whatever value the other operator was holding.
So, the formula then simplifies as follows:


r = a ^ (a ^ b);

which is equal to


r = b;

because we when we apply twice the same value using XOR on another value, we revert back to the original value (so the second ^a nullifies the first ^a)

 

When a >= b then the formula will change as follows:


r = a ^ ((a ^ b) & 0x00000000);

When one of the operators on a bitwise AND operation is composed only from 0s, then the result is always 0 no matter what value the other operator was holding.
So, the formula then simplifies as follows:


r = a ^ (0x00000000);

which is equal to


r = a;

because when one of the operators in a XOR operation is only composed from 0s then the result will be the value of the other operator, no matter what it was.

 

Full example

Below you will find a full example that compares the execution speed of the two methods by executing each several thousands of time on the same random data.

[download id=”3875″]


#include <stdio.h>
#include <time.h>
#include <stdlib.h>

int main() {
    {
        const clock_t start = clock();

        srand(10);
        unsigned long int i;
        unsigned int max = 0;
        for (i = 0; i < 1000000000; i++) {
            const int a = rand();
            max = max < a ? a : max;
        }
        const clock_t end = clock();
        const float seconds = (float) (end - start) / CLOCKS_PER_SEC;
        printf("Seconds elapsed %f\tIf statement. Overall max value = %u\n", seconds, max);
    }

    {
        const clock_t start = clock();

        srand(10);
        unsigned long int i;
        unsigned int max = 0;
        for (i = 0; i < 1000000000; i++) {
            const int a = rand();
            max = a ^ ((a ^ max) & -(a < max));
        }
        const clock_t end = clock();
        const float seconds = (float) (end - start) / CLOCKS_PER_SEC;
        printf("Seconds elapsed %f\tBitwise operation. Overall max value = %u\n", seconds, max);
    }
    return 0;
}

Results

Our results show that using the traditional if statement with assignment is faster than using our formula as expected.
Which makes sense as there is an if statement in the formula as well and then additional operations to get the result, instead of just the assignment.

Seconds elapsed 5.770000 If statement. Overall max value = 2147483647
Seconds elapsed 6.180000 Bitwise operation. Overall max value = 2147483647

10 times bigger input

Seconds elapsed 57.450001 If statement. Overall max value = 2147483647
Seconds elapsed 63.869999 Bitwise operation. Overall max value = 2147483647