Click here to Skip to main content
16,019,976 members
Articles / Programming Languages / C
Article

Fast Algorithm to check the numbers 2^n

Rate me:
Please Sign up or sign in to vote.
4.55/5 (23 votes)
12 Dec 2002 66.1K   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!

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here


Written By
Web Developer
Hong Kong Hong Kong
Still alive

Comments and Discussions

 
GeneralC# Trick Pin
KK Adams30-Jun-08 16:12
KK Adams30-Jun-08 16:12 
GeneralRe: C# Trick Pin
Member 150696612-Jun-09 9:36
Member 150696612-Jun-09 9:36 
GeneralMod - Works for n = 0 Pin
User 238229218-Feb-08 19:04
User 238229218-Feb-08 19:04 
GeneralFFT in Visual C++ Pin
Anonymous7-Jul-03 1:18
Anonymous7-Jul-03 1:18 
GeneralQuick Mod for 2^0 and others Pin
ColinDavies27-Dec-02 14:16
ColinDavies27-Dec-02 14:16 
GeneralRe: Quick Mod for 2^0 and others Pin
nutty21-Mar-06 6:23
nutty21-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
GeneralThanks... Pin
Rocky1010-Dec-02 3:36
Rocky1010-Dec-02 3:36 
GeneralHacker's Delight by Warren Pin
George V. Reilly9-Dec-02 15:58
George V. Reilly9-Dec-02 15:58 
GeneralMake it slightly faster... Pin
KevinHall5-Dec-02 18:08
KevinHall5-Dec-02 18:08 
GeneralHmmm.... Pin
Nitron5-Dec-02 17:38
Nitron5-Dec-02 17:38 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.