BOB LAT BOB LAT - 2 months ago 8
C Question

Completely removing most significant bit

I don't know how to proceed with this...
I want to change a binary stored as an int

1111
to
111
being stored as an int also?

Answer

I don't ordinarily answer "gimme teh codez" questions, but it was an interesting problem so I did it for fun. As usual, most of the time went into extraneous stuff like the output code.

If this is homework, do take the time to understand how the code works, or you'll only be cheating yourself.

#include <stdio.h>
#include <string.h>

// Define "number" as an unsigned number of desired size
typedef unsigned long number;

number drop_msb(number n);
char *ntob(char *dest, number n, int min_len);

int main()
{
    number i;
    number j;
    char ibuf[65];
    char jbuf[65];

    for (i = 0; i < 512; i++) {
        j = drop_msb(i);
        ntob(ibuf, i, 0);
        ntob(jbuf, j, strlen(ibuf) - 1);
        printf("%s --> %s\n", ibuf, jbuf);
    }

    return 0;
}

number drop_msb(number n)
{
    number bit;
    number a;

    // Handle special case
    if (n == 0)
        return 0;

    // Set highest bit
    bit = ((number) -1 >> 1) ^ (number) -1;

    // Guaranteed to terminate
    while (1) {
        a = n ^ bit;
        if (a < n)
            return a;
        bit >>= 1;
    }
}

char *ntob(char *dest, number n, int min_len)
{
    /* Convert n to shortest binary string, padding with zeroes on left
     * to make it at least min_len characters long. dest should be long
     * enough to hold the maximum number, plus terminating null. */

    char *left;
    char *right;

    /* min_len should be >= 1, to handle n == 0 correctly. Also needs to
     * be non-negative to avoid bad pointer during padding. */
    if (min_len < 1)
        min_len = 1;

    // Build with lsb on left
    for (right = dest; n; right++, n >>= 1)
        *right = '0' | (n & 1);

    // Pad if needed
    while (right < dest + min_len)
        *right++ = '0';

    *right = '\0';

    // Reverse it
    for (left = dest, right--; left < right; left++, right--) {
        *left ^= *right;
        *right ^= *left;
        *left ^= *right;
    }

    return dest;
}
Comments