Two useful and ingenious algorithms

[Accname]

Hi guys, just wanted to share with you 2 very useful and ingenious algorithms which i found across the interwebs.

The first one checks if a given integer number is a power of two:

private boolean is_power_of_two(int value){
        return (value & (~value + 1)) == value;
}

Its incredibly fast and effective and i love the solution. The best i have ever seen in fact.
The algorithm checks the number of "1's" in the binary representation of value.
To do this the algorithm calculates the two-complement of the value and connects them with a logic AND.
Only if value has only a single 1 in its binary representation this method will return true.

The next algorithm calculates the next biggest power of two for a given integer:

private int next_power_of_two(int value){
        value--;
        value |= value >> 1;
        value |= value >> 2;
        value |= value >> 4;
        value |= value >> 8;
        value |= value >> 16;
        value++;
        return value;
    }

As far as i understood this algorithm finds the highest 1 in the binary representation of value, then makes every position in the binary representation, which comes before the highest 1, a 1 as well.
Then, when we add 1 at the end, all the 1's in binary will become a zero exept for the next highest position which has been a zero before.
This is really complicated to explain, its best to try it oneself with an example value.

Lets say we take the value 5, in binary represented as 0101.

Now we sutract 1 and get 0100. # value--;

we shift 0100 one position to the right and OR the result with 0100 => 0110 # value |= value >> 1;

we shift 0110 two positions to the right and OR the result with 0110 => 0111 # value |= value >> 2;

we shift 0110 four positions to the right and OR the result with 0110 => 0111 # value |= value >> 4;

we shift 0110 eight positions to the right and OR the result with 0110 => 0111 # value |= value >> 8;

we shift 0110 sixteen positions to the right and OR the result with 0110 => 0111 # value |= value >> 16;

We now add 1 to the result and get: 0111 + 1 = 1000 = 8


Just wanted to share these 2 gems with you guys.

 

[Fatmankev]

Cool man. I can't exactly picture where this would be applied, but I'm glad you found somethin' that'll work well for you, and I hope someone else that can truly appreciate it comes across it.

 

[Accname]

Cool man. I can't exactly picture where this would be applied, but I'm glad you found somethin' that'll work well for you, and I hope someone else that can truly appreciate it comes across it.

Most graphics cards can only load textures whichs width and height is a power of 2.
Of course an image, like a png or something, doesnt need to be a power of 2 in width or height.
So if you want to load a png into your graphics card you have to convert it to an image with the next highest power of 2 in width and height.
Just one use for these algorithms.

For example: I know that the texture-loader from the slick library uses an algorithm for this which is way worse. It calculates all powers of 2 from 1 up to either the size of the image or above.

 

[s3rius]

Most graphics cards can only load textures whichs width and height is a power of 2.

Actually most modern and semi-modern graphics cards can load non-power-of-2 textures.

In OpenGL NPOT support is core since version 2.0 (which came out in mid 2004).
DirectX supports NPOT conditionally since 9.0 (late 2002) and unconditionally since 10.0 (2006).

All graphics card which are at least OGL 2.0 or DirectX 10.0 capable must either support any size of texture natively or the driver handles rescaling on its own.

But I can think of plenty other opportunities to use these functions:

When using bitmasks it can be used to see if only 1 bit (1 option) is flipped.

For number compression you might want to get the next higher power of 2 in order to know how many bits you need to store a number.

It can be used to find the minimal depth of a binary tree given you only know the number of nodes in the tree.

I'm sure there is a myriad of other uses. Cool stuff