Category Archives: Code.Fu

Code.Fu: Quickly testing if a positive integer is a power of 2.

by

0

If you are a graphics programmer you will often need to test if an integer is a power of 2. To do this you can exploit a neat trick using binary arithmetic. This trick will work with all positive integers.

Lets say the number you are testing is 4. Take a look at the simple binary arithmetic below:


  4 --> 0100‬ (binary)
- 1 --> 0001
------------------
  3 --> 0011

  4 --> 0100
& 3 --> 0011
------------------
  0 --> 0000

In short, you subtract 1 from the number and do a binary ‘AND’ of the result and the original number. If the number is a power of two, the result you get will always be 0.  The only exception is 0 itself, which will return 0 in the above operation. Depending on your application you may or may not want that.

C/C++:

#define bool int /*remove this line for C++*/

bool is_powof_2(int x)
{ 
  return ((x & (x-1)) == 0);
}

bool is_powof_2_excl_0(int x)
{ 
  return (x != 0) && ((x & (x-1)) == 0);
}

Python:

def is_powof_2(x):
	return ((x & (x-1)) == 0)

def is_powof_2_excl_0(x):
	return (x != 0) and ((x & (x-1)) == 0)

Angle between 2 vectors.

by

0

Anybody and everybody who has worked with 3D has, at one point or the other, run into a situation where an angle between 2 vectors was needed. The solution is rather straight forward; take the dot-product and take an arccosine of it. That’s it, you have the angle between the two. Well yes, but then again I wouldn’t be writing this blog entry if there wasn’t a story behind this. Yes, the above method will definitely give you the angle between vectors; well most of the times anyways. It’s mathematically correct. However, taking the arccosine (acos) can be prone to floating point overflows and can cause simulations and calculations to go out of whack unexpectedly. That’s because the acos function in the standard library operates in the range between [-1, 1]. Values very near to the extreme range values can cause the function to give out strange angle values and\or will give exceptions if the range values are exceeded even slightly. It’s not always you can clamp these values to prevent error, especially in situations where smooth transition of angles is required. Clamping the values will cause a jerk in the simulation and might reduce precision if it were required.

So what do we do in such a case?  Don’t worry there is a solution. Instead of using acos use atan2. atan2 takes two arguments (x,y) and finds the counterclockwise angle in radians between the x-axis and the point (x, y) in 2-dimensional Euclidean space. More importantly it is valid for all values of x and y except (0, 0) which is the origin btw. It uses the signs of both arguments to determine the quadrant of the result. The x and y in our equation are simply perp-dot-product and dot-product respectively, or simply put

angle = atan2( magnitude(cross(a,b)),  dot(a,b) );

Just remember one thing, atan2 will give you the results in the range -pi to pi radians. So you may (or may not) have to adapt your code to handle that.