Determine if number is in the binary sequence 1 2 4 8 16 32 64 etc

Question

Possible Duplicate:
How to check if a number is a power of 2

I want to determine if a number is in

1 2 4 8 16 32 64 128 256 512 1024 2048 4096 8192 16384 ...

I tried this:

public static void Main(string[] args)
{            
    int result = 1;  
    for (int i = 0; i < 15; i++)
    {          
        //Console.WriteLine(result);
        Console.WriteLine(result % 2);
        result *= 2;

    }  
}

As you can see it returns 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ...

How should I efficiently make the above print to be 0 for all of them including 1?

I know the code works as expected. My question is what code to write to print what **I** expect. — Shimmy Weitzhandler, Feb 13 '12 at 11:57
@CodeInChaos, I voted myself to close it. Thanks for the reference. — Shimmy Weitzhandler, Feb 13 '12 at 12:38
For bit fiddling questions, there is often an answer at: http://www-graphics.stanford.edu/~seander/bithacks.html#DetermineIfPowerOf2 — CodesInChaos, Feb 13 '12 at 12:39

Sam Greenhalgh · Accepted Answer · 2012-02-13T12:29:44.220

15

The following expression should be true if i is in your sequence.

(i & (i-1)) == 0)

http://rextester.com/JRH41036

edited Feb 13 '12 at 12:29

answered Feb 13 '12 at 11:57

Sam Greenhalgh

5,952
21
37

2

that's a really useful site to know about. – Antony Scott Feb 13 '12 at 12:46
@zapthedingbat, yep. that's exactly what I was looking for. – Shimmy Weitzhandler Feb 13 '12 at 13:09

MByD · Answer 2 · 2012-02-13T12:09:56.750

2

Since the first time result is odd, you will get 1, since right after that you multiply it by 2, you will always get 0.

You need to print result if you want to get the list of powers of 2.

Console.WriteLine(result);

A primitive way to do that will be:

public static void Main(string[] args)
{            
    int result = 1;  
    int numToCheck = 141234;
    boolean found = false;
    for (int i = 0; i < 15; i++)
    {          
        if (numToCheck == result) {
            found = true;
            break;
        }
        result *= 2;
    }  
    if(found) Console.WriteLine("Awesome");
}

edited Feb 13 '12 at 12:09

answered Feb 13 '12 at 11:51

MByD

135,866
28
264
277

1

What I want is just to determine if `result` is of the binary sequence `1, 2, 4, 8` etc. – Shimmy Weitzhandler Feb 13 '12 at 11:53
He don't want to write that list i seems, but to know whether any given number is part of that sequence, but that is quite hard to understand given his code. – Øyvind Bråthen Feb 13 '12 at 11:54
You do exactly that. Result is 1 in the first run, then 2, then 4, then 8, then 16, then 32, then 64 and so on. – Sebastian P.R. Gingter Feb 13 '12 at 11:55
What if the number to check is greater than 2^15? – Øyvind Bråthen Feb 13 '12 at 12:00
@ØyvindKnobloch-Bråthen - this is a primitive example only, I tried to make the idea clear. not to provide a full implementation. – MByD Feb 13 '12 at 12:02
@BinyaminSharet - Not to be to critizing here, but he asked for a efficient solution, then you should at least stop searching when you found your answer, and not carry out the full 15 iterations regardless. Adding a break after setting found to true should be in place here :) – Øyvind Bråthen Feb 13 '12 at 12:08
@ØyvindKnobloch-Bråthen - you are absolutely right. I meant to add it but forgot :) – MByD Feb 13 '12 at 12:09

score 2 · Answer 3 · edited May 23 '17 at 12:31

2

You can determine if a number is a power of 2 (including 2^0) by using the following method:

public bool IsPowerOfTwo(int x) {
    return (x > 0) && ((x & (x - 1)) == 0)
}

Over here you can read why and how this works.

edited May 23 '17 at 12:31

Community

1
1

answered Feb 13 '12 at 11:58

Dennis Traub

50,557
7
93
108

Woops, true. I got it completely wrong, will update. ... Done. – Dennis Traub Feb 13 '12 at 12:00
I'd use `x>=0`, so all negative numbers get rejected. Or throw an `ArgumentOutOfRangeException` if `x<0`. – CodesInChaos Feb 13 '12 at 12:28
@CodeInChaos thanks, modified accordingly. As an alternative you could use a parameter of type `uint`. – Dennis Traub Feb 13 '12 at 12:50

score 2 · Answer 4 · answered Feb 13 '12 at 11:59

How about something like this?

bool IsInBinarySequence( int number ){
  var numbertocheck = 1;
  do{
if( number == numbertocheck ) return true;
numbertocheck *= 2;
  }while( numbertocheck <= number );
  return false;
}

This has no specific limit on the number to check, but makes sure it stops checking if the number to check grows larger than the actual number we're trying to decide if is in the binary sequence.

Yahia · Answer 5 · 2012-02-13T12:07:09.883

What you is not a test whether the number is in the sequence BUT it is a generator for such numbers... only the print part is containing some sort of a test...

Try this code for a test:

public static void Main(string[] args)
{            
    int result = 0;  
    int numToTest = 0;
    if ( int.TryParse (args[0], out numToTest) )
    {
       result = ((from c in Convert.ToString (numToTest, 2) where c == '1' select c).Count() == 1 ) ? 1 : 0;
    }

    Console.WriteLine(result);
}

The above code takes a commandline argument and tests it for being in the binary sequence according to the criterion you posted... if so it prints 1, otherwise it prints 0.

This seems like a good solution :) +1 – Øyvind Bråthen Feb 13 '12 at 12:06 — Øyvind Bråthen, Feb 13 '12 at 12:06

score 1 · Answer 6 · answered Feb 13 '12 at 12:00

1

It's a bit of a hack, but this works ...

    static void Main()
    {
        for (int i = 0; i < 40; i++)
        {
            var str = Convert.ToString(i, 2);
            var bitCount = str.Count(c => c == '1');
            Console.ForegroundColor = bitCount == 1 ? ConsoleColor.White : ConsoleColor.DarkGray;
            Console.WriteLine(i + ": " + (bitCount == 1));
        }
    }

it seems you're actually asking if only one bit in the binary representation of the number is a 1

answered Feb 13 '12 at 12:00

Antony Scott

21,690
12
62
94

1

Why does color get mixed up into a method checking if a number is in a specific series of numbers? – Øyvind Bråthen Feb 13 '12 at 12:02
because it's an example and i thought it would help highlight when the condition was met – Antony Scott Feb 13 '12 at 12:09
I didn't read correctly here it seems. Didn't see you setting the console foregroundcolor. Then it seems fine :) – Øyvind Bråthen Feb 13 '12 at 12:10

score 0 · Answer 7 · answered Feb 13 '12 at 11:54

Thats correct. 1 0 0 0 0 0 is the correct sequence. Result is 1 in the first loop. 1 % 2 is 1. Then result *= 2 gives result the value 2. In the next loop run 2 % 2 = 0. Then result *= 2 is 4. 4%2 is 0. 4 *= 2 is 8. 8 %2 is 0. Since result is always multiplied with 2 it keeps to be in the powers of 2 row and thus als MOD operations with 2 result to 0. So all is fine with that code.

score 0 · Answer 8 · answered Feb 13 '12 at 11:56

0

your code will print only Binary sequences. as you are applying MOD 2 . so either you will get 0 or 1 . so it will be print in Binary Sequence.

answered Feb 13 '12 at 11:56

Ravi Gadag

15,735
5
57
83

score 0 · Answer 9 · answered Feb 13 '12 at 11:58

Boolean result = false;
Int32 numberToTest = 64;
Int32 limit = 15;

for (int i = 0; i < limit && !result; i++)
{
    if (Math.Pow(2, i).Equals(numberToTest))
    {
        result = true;
    }
}

Console.WriteLine(String.Format("Number {0} {1} a power of 2.", numberToTest, result ? "is" : "is not"));

Determine if number is in the binary sequence 1 2 4 8 16 32 64 etc

9 Answers9