15,991,686 members
Articles / Programming Languages / C
Article

Fast Algorithm to check the numbers 2^n

Rate me:
12 Dec 2002 65.7K   25   10
Optimised code for valid data length to FFT

Introduction

Some applications of signal processing, like Fast Fourier Transform (FFT) need the length of sampled-data input equal to 2^n (where n : integer, n=1,2,3,...), and requires fast testing for this number. This test must be done in a very short time especially in real-time applications operated in DSP cart (as in TMS320C6xxx DSP). Here is an optimized code snippet for this purpose.

Source code

The following function return `TRUE` if the number x has the form 2^n

```bool CheckInputToFFT(int x)
{
return (!(x & (x-1)));
}```

That's all, which means each of the numbers (2,4,8,16,...2^n) gives zero when ANDed with previous number!

A list of licenses authors might use can be found here

Written By
Web Developer
Hong Kong
Still alive

 First Prev Next
 Re: C# Trick Member 150696612-Jun-09 9:36 Member 1506966 12-Jun-09 9:36
 Mod - Works for n = 0 User 238229218-Feb-08 19:04 User 2382292 18-Feb-08 19:04
 FFT in Visual C++ Anonymous7-Jul-03 1:18 Anonymous 7-Jul-03 1:18
 Quick Mod for 2^0 and others ColinDavies27-Dec-02 14:16 ColinDavies 27-Dec-02 14:16
 Re: Quick Mod for 2^0 and others nutty21-Mar-06 6:23 nutty 21-Mar-06 6:23
 is it possible that this assumption is not always correct? if you change it to ` return (!(x & (x-4)));` You don't get all multiples of 4, missing 12, 20, 24, 28.. the result is rather the powers of 2 and the numbers below 4 taken away. By the way, since we were looking for multiples of 2 I suggest that a good change would do the same with 4, like looking for powers of 4. This is also not true for the above formula. Or did I get something wrong? Ingo
 Thanks... Rocky1010-Dec-02 3:36 Rocky10 10-Dec-02 3:36
 Hacker's Delight by Warren George V. Reilly9-Dec-02 15:58 George V. Reilly 9-Dec-02 15:58
 Make it slightly faster... KevinHall5-Dec-02 18:08 KevinHall 5-Dec-02 18:08
 Hmmm.... Nitron5-Dec-02 17:38 Nitron 5-Dec-02 17:38
 Last Visit: 31-Dec-99 18:00     Last Update: 9-Sep-24 2:31 Refresh 1