Bit Operations: round a number to a next multiple of a power of 2

This is easier than the last bit operation post. By the way, I would like to thank "LOLmachine" for the comments - improvements in the last bit operation post....

Anyway...Multiples of a power of 2 share the property that have at least a fixed number of digits zero in the least significant position. So, all multiples of 2 have the 1 first bits zeroed, all multiples of 4 have the 2 digits zeroed, etc.

In order to round a number (x) to the next multiple of "a", where "a" is a power of 2 all you need to do is to compute this:

round(x) = (x + (a-1)) & ~(a-1)

SO, if a is 8, the above formula looks like this:

round(x) = (x + 7) & ~7;

round(14) = (14 + 7) & (~7) = 16
round(16) = (16 + 7) & (~7) = 16
round(17) = (17 + 7) & (~7) = 24

multiple gcc versions in Slackware 12.0

Slackware's default compiler nowadays is gcc-4.1.2. If you need an older compiler from the 3.x series, then you may use the one from the pasture directory of the distribution.

The problem is that you cannot have them both, because the two packages have files with the same name. So, if you try to use installpkg to install the older compiler the installer will overwrite some gcc-4.1.2 files.

Fortunately, you don't need to compile gcc by your self. Eric Hameleers (alien bob) maintains an unofficial slackbuilds repository hosted in slackware. There is a gcc package: http://www.slackware.com/~alien/slackbuilds/gcc34/ which is compatible with the official one.

latex and footnotes

In latex if you have a footnote and a figure with b (bottom) placement attribute on the same page, then the figure will be placed under the footnote. The result is really ugly....

I was searching for a way to fix this. Of course the straight-forward solution is to use the h (here) attribute in the figure and put the figure's code in the position you want, but this is not the best thing to do.

Well.. there is a way to force the footnotes to be always placed at the bottom of the page. You can do this by using the footmisc-package. By using this package you can change the default typesetting of footnotes. If you include the line:

\usepackage[bottom]{footmisc}

in latex preamble you get the desired footnotes behavior.

Bit Operations: find first zero bit

If anybody cares here is an algorithm to find the first zero bit in a number:

1. Invert the number
   
2. Compute the two's complement of the inverted number
3. AND the results of (1) and (2)
   
4. Find the position by computing the binary logarithm of (3)
   

e.x.
For the number 10110111

1. 01001000
2. 10111000
3. 01001000 AND 10111000 = 00001000
4. log2(00001000) = 3

But in a x86 processor environment there is a more simple way to do this since Intel provides a specific assembly instruction for this purpose called bsfl. This instruction return the position (index) of the least significant bit set to 1 in a 32-bit word. By using inline assembly, someone can easily create a function that finds the first zero bit by inverting a number and feeding it to this instruction. For 8-bit numbers, the code for this in gcc would look like this:

/*
 * find the position of the first 0 in a 8-bit array
 */
inline unsigned short find_first_zero(uint8_t bit_array)
{
    unsigned pos = 0;

    __asm__("bsfl %1,%0\n\t"
        "jne 1f\n\t"
        "movl $32, %0\n"
        "1:"
        : "=r" (pos)
        : "r" (~(bit_array)));

    if (pos > 7)
        return 8;

    return (unsigned short) pos;
}