Checking whether a number is a power of 2

bool IsPowerOfTwo (int value)
{
  return (value & -value) == value;
}

the good old trick

indeed. good to get the algorithms and code snippets filled with such stuff. thats what its ment for!

hmm... let's hope people use the search function in this forum, unlike other places we don't want to mention

another one

bool IsPowerOf2( int value ) 
{
  return ! (value & ( value - 1 ) ); 
}

Originally Posted by anubis

hmm... let's hope people use the search function in this forum, unlike other places we don't want to mention

[snapback]9650[/snapback]

indeed...

lets see if we find some bether solution to it.. would be nice..

For two more useful functions which round to the next bigger / next smaller power of two, see: http://www.flipcode.com/cgi-bin/fcarticles...show=4&id=64182

Originally Posted by john

bool IsPowerOfTwo (int value)
{
  return (value & -value) == value;
}

It is not going to work for if the numbers are = 1, 0, -1....
Can give you solution in that case

this solution will not work for if if the number = 1, 0, -1....
need some thing like return (value != 0) && (value != 1) && ( ( (value-1) & value ) == 0 );
but still need to modify

Originally Posted by thakurna

It is not going to work for if the numbers are = 1, 0, -1....

Only not for zero. 1 & -1 == 1, which is correct as 1 is a power of two (2^0 to be exact). -1 & 1 is of course also 1, but now 'value' is -1 so the end result doesn't equal 'value', therefore it is not a power of two (this works for every negative value btw)

Only the zero is a special case. So it would be:

bool IsPowerOfTwo(int value)
{
    return value ? ((value & -value) == value) : false;
}

Is a bitwise "&" consistent across platforms?? Just curious...

Alex

It depends what language standards the compiler follows but for the most cases yes.

What?

I've never heard of bitwise & not being consistent. That wouldn't be "not adhering to standards", that would be a *bug*.

Unless I'm missing something. Mihail121, do you know of a compiler that doesn't handle this?

I'd find it incredible to hear that there's a "standard" that defies normal bitwise &. It's like saying that my compiler has a different standard for "+".

Well, bitwise & ought to work the same way everywhere, but not all machines are two's complement and so some of the formulas posted above will not always work. (Realistically though, any machine you are going to be writing code for nowadays uses two's complement for integer arithmetic.)

Indeed, the standard requires signed ints to be either two's complement, one's complement or sign and magnitude. But that doesn't really matter, it only means we cannot use the negation operator in our test code. So either use bladder's, or this:

bool IsPowerOfTwo (int value)
{
  return (value & (~value+1)) == value;  //~value+1 equals a two's complement -value
}

I wonder why there is no support for "flags" that indicate what kind of system the code has been written for (little endian, pointer size, etc etc).
That way the compiler could easily "fix" the code (or rather change the output to do what we meant it to do) if the current target doesn't fit the flags. Why is it up to us to worry about all that crap?
Using the flags it should be inherently clear what the code is supposed to do..

Sorry to high jack the thread but this is probably not worth starting a new one..

Alex

Because C has been designed to write OS with, you're supposed to know what you're doing.
As it is the Standard is byzantine enough, it doesn't need even more assumptions.

Use the right tool for a given task.
If you want more abstraction from the hardware, use another language.
If you want less, write some asm.

Now I'm probably not the only one who want's to write portable C++ code. Also the feature I suggest wouldn't stop anyone from writing OS code..it's less a language thing, more of a compiler option. There is no good reason I can see to have interpretations of my code that I have no control over but which alter the logic.

Originally Posted by Alex

it's less a language thing, more of a compiler option.

If it's not into the language/standard, then it's not portable across compilers.

So either you don't want to have to handle such issues and use another language that insulates you better, or rely on something like autoconf.

Originally Posted by Alex

There is no good reason I can see to have interpretations of my code that I have no control over but which alter the logic

The only logic that is altered is the one you _think_ your code implements.
The compiler only care about how your code should be interpreted vs the Standard.
It doens't read into your mind yet

tbp: you are missing the point. For example, the standard states that the number of bits in a char shall be 8 or more. Fortunately, the standard also states that there shall be a CHAR_BIT constant representing the number of bits in a char. It also defines other handy constants like INT_MAX. These are all pretty implementation defined, but the point is that you have access to such constants, so you can write portable code that runs on different architectures using these constants.

Unfortunately for endianness and how signed integers are represented, there is no such thing.

Again, portability has never been part of the set of problems C has been designed to solve.

It's just a thin abstraction layer from the metal, some souped assembler.
By design and for varied reasons like efficiency and compiler complexity.

If portability is your prime concern you shouldn't be using C (or any of its descendant) in the first place.

So, i'm not missing any point, you're just barking at the wrong tree.

Bjarne Stroustrup lists C++ as a general-purpose language with a bias to "generic programming" (among others including OS stuff):
http://www.artima.com/cppsource/cpp0x.html
Where "Generic programming is about generalizing software components so that they can be easily reused in a wide variety of situations."
So I agree that total portability is NOT an explicit! goal of the standard.
Reuseability on the other hand means that portability is desired where it doesn't hurt the standard (or the target specific constrains).
Also note that at least I'm talking about C++, not C.
Which language(s) to use depends on the problem at hand. I doubt that a desire for portability prohibits using C++.

ALex

Portability isn't and never was an explicit goal of the C++ Standard for a good reason, let me cite the prophet himself:

Originally Posted by Bjarne Stroustrup

C++'s C compatibility was a key language design decision rather than a marketing gimmick. Compatibility has been difficult to achieve and maintain, but real benefits to real programmers resulted, and still result today.

You can talk genericity and OOness all day long, C++ is by design compatible with C.
Thusly, regarding portability they both stand side by side.

The C++0x improvements should be done in such a way that the resulting language is easier to learn and use. Among the rules of thumb for the committee are:
Provide stability and compatibility (with C++98, and, if possible, with C)

Being compatible with C is nice but rather optional ("if possible").

This is getting no where so this will be my last post on this...

ALex

Your quote is about C++0x, an extension to C++ (just like C99 was an extension of C).

If that compatibility is news to you, i'm sorry, but you should have asked yourself why you could happily (void *) everything, among other things.