rand


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

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.

Bitwise-Max.c (compressed) (140 downloads)

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

C/C++: Get a random number that is in a specific range

Assuming you need to generate a random number that is in a specified range, you can do the following:

//int rand(void) creates a pseudo-random number in the range of 0 to RAND_MAX
//RAND_MAX is defined in stdlib.h and is the largest number rand will return (same as INT_MAX).
const int new_number = (rand() % (maximum_number + 1 - minimum_number)) + minimum_number;

The above code first creates a pseudo-random number that is in the range of [0, RAND_MAX].
Then it will divide it with the width (+1) of the range we want to use (maximum_number + 1 - minimum_number) and get the remainder (modulo).
The modulo will be in the range of [0, maximum_number - minimum_number], so we add to it the value of minimum_number to shift the result to the proper range.
This solution, as demonstrated in the example below, works for negative ranges as well.

Full example of generating 100000 random numbers that are all in the range [-31, 32].

const int maximum_number = 31;
const int minimum_number = -32;
unsigned int i;
for (i = 0; i <= 100000; i++) {
	const int new_number = (rand() % (maximum_number + 1 - minimum_number)) + minimum_number;
	printf("%d\n", new_number);
}

C: Code to time execution with accuracy greater than a second

The following application computes the time needed for a process to finish using the method clock().
The result of the application is the time in seconds as a floating number (where 1.0 = 1 second).
It provides greater accuracy than seconds as the estimation is done using processor time used by the program.

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

int main()
{

    /* clock_t clock(void)
     The clock() function returns an approximation of processor time used by the program.
     The value returned is the CPU time used so far as a clock_t,
     to get the number of seconds used, divide by CLOCKS_PER_SEC.
     On error it returns -1. */
    const clock_t start = clock();

    /* svoid srand(unsigned int __seed)
     The srand() function sets its argument as the seed for a new sequence of pseudo-random
     integers to be returned by rand(). These sequences are repeatable by calling srand() with the
     same seed value.
     If no seed value is provided, the rand() function is automatically seeded with a value of 1. */
    /* time_t time(time_t *__timer)
     time() returns the time since the Epoch (00:00:00 UTC, January 1, 1970), measured in seconds.
     If the __timer variable is not NULL, the return value is also stored there. */
    srand(time(NULL));
    unsigned long i;
    for (i = 0; i < 10000000; i++)
    {
        /* int rand(void)
         The rand() function returns a pseudo-random integer in the range 0 to RAND_MAX inclusive. */
        rand();
    }
    const clock_t end = clock();

    /* ISO/IEC 9899:1999 7.23.1: Components of time
    The macro `CLOCKS_PER_SEC' is an expression with type `clock_t' that is
    the number per second of the value returned by the `clock' function. */
    /* CAE XSH, Issue 4, Version 2: <time.h>
    The value of CLOCKS_PER_SEC is required to be 1 million on all
    XSI-conformant systems. */
    const float seconds = (float) (end - start) / CLOCKS_PER_SEC;

    printf("Seconds elapsed %f\n", seconds);
    return 0;
}

How to randomize order of rows in Excel

In the following video we demonstrate how to randomize the rows of an Excel sheet.

Methodology:

  • We created a new column next to the data we want to randomize their order, then we typed in the first cell the following formula =rand().
    =rand() will generate a random value between 0 and 1.
  • After that we applied the same formula to the entire column.
  • To apply the formula to the whole column we used a very simple method: we double-clicked on the bottom right hand corner of the cell .

Apply formula to whole column by double clicking on the bottom right corner of the cell

  • Later, we sorted our date using the column of random values.
  • Finally, we deleted the new column.

 

Alternative way to copy the formula to the entire column:

  • Including the cell with the formula, select the cells in the new column that you want the new formula applied to (all the rows you want to be randomized) and the press Ctrl+D.