• Post Reply Bookmark Topic Watch Topic
  • New Topic

return true if a integer is power of 2  RSS feed

 
hhd chen
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Given an integer, write a method to retrun ture if integer is power of 2, for example, 2,4,8,16,32.
Please use while loop.
Actually ,it is interview question I have been ever asked.
appreciate your help.
 
marc weber
Sheriff
Posts: 11343
Java Mac Safari
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Any ideas?
 
Vikas Kapoor
Ranch Hand
Posts: 1374
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
This may help you.The input value 1(number = 1) can be handled as a special case.

 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Likes 1
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Please don't simply give answers like that. The idea is for people to learn, and giving an answer doesn't teach anyboyd anything.
 
Gavin Tranter
Ranch Hand
Posts: 333
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Wow, long answer vishal.

Seems a long way to get the power of 2.
I just did a quick serach and there is a much much faster way.

Gavin
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hm, it might be helpful to consider the full range of numbers that could be passed into that method. Does it give correct results for all possible int values?

For added fun, what's the fastest implementation you can come up with? For this question, you may ignore the requirement about using a while loop. Use any code that gives a correct answer.
 
Vikas Kapoor
Ranch Hand
Posts: 1374
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Campbell Ritchie:
Please don't simply give answers like that. The idea is for people to learn, and giving an answer doesn't teach anyboyd anything.


I don't feel so. S/He can analyse at her/his end.
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Jim Yingst:
Hm, it might be helpful to consider the full range of numbers that could be passed into that method. Does it give correct results for all possible int values?
No, it doesn't.
 
Vikas Kapoor
Ranch Hand
Posts: 1374
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hello Jim,

Where does it fail?
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Gavin Tranter:
I just did a quick serach and there is a much much faster way.
Yes, it is much better.

And Vishal, the idea of the Ranch is for people to work out their solutions with our help. There are cases where the poster reuires a straight answer, but this is probably not (yet) one of them.
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Vishal Pandya:
Hello Jim,

Where does it fail?
If (n <= 0)
 
Vikas Kapoor
Ranch Hand
Posts: 1374
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Campbell Ritchie:
Yes, it is much better.

And Vishal, the idea of the Ranch is for people to work out their solutions with our help. There are cases where the poster reuires a straight answer, but this is probably not (yet) one of them.


Hey comeon i tried my best. That's it. There could be many.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Why search, Gavin? If you couldn't find a better answer on your own, you're not really in a position to criticize, are you?

There's a shorter way, and there's a faster way. They aren't necessarily the same. Well, there's a way that is both slightly shorter and slightly faster than Vishal's code, but there is another way that's even shorter, and another that is even faster.
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I think we are going to have to agree to differ, Vishal.

There is a nice way to do it with a recursive algorithm, but when I followed Gavin's example with Google there was a single line solution.
 
Gavin Tranter
Ranch Hand
Posts: 333
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Perhaps not
But in this case I feel I can.
Cos I knew there was a better answer, no I didnt know what that was, but just my "gut" reaction, that and the fact that 2 was setting off alarm bells, made me go search.
Also I had to read the code a few times to figure out its intent. (Probably more to do with my relative dumb-ness, I wont be winning any programming challenges anytime soon )

Plus i was about to answer a different question, I mixed up the "power of" question with the "factor of" question, yet again proving I should read "exam questions" more carefully.

 
hhd chen
Greenhorn
Posts: 4
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Campbell,

I am weak in coding. so I need sample code to educate myself.
Can you give me one of your solution?
Thanks!

Henry
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
HHD, the best way to become a better programmer is to learn by writing programs yourself, not just studying what others write. So I'm not going to give you answers. Vishal already gave you one anyway. Instead I'll give some ideas. Try working on any of these ideas, and show us what you're trying. We're happy to help, but you will learn much more if you do more of the work yourself.

For one (very short, kind of slow) solution: think about what number like 1, 2, 4, 8, 16 etc look like in binary. What do they have in common? Now look at the Integer class. Do you see any method that could help you test this?

A nice recursive solution would be similar to Vishal's solution. (You might want to see if you can fix it to work for negative numbers first.) Test if the number is divisible by two. If not, it's not a power of two. If it is, then test if n/2 is a power of two as well.

For another solution (longer but very fast): forget about loops and recursion. What are all the possible ints that are powers of two? Is there a way to list all of these? There are several ways to do this, but one is particularly fast. Well, two are really fast, but one of those two also uses a huge amount of memory, so it's a bad idea. The other way is very fast and does not require much memory.
[ April 15, 2008: Message edited by: Jim Yingst ]
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
ok here's the solution

public class TestPrint
{
public static void main(String args[])
{
int num = 32;
int other = 1;
if(((~num) & 1) == 1)
{
System.out.println("The number is a power of two");
}
else
System.out.println("The number is a NOT A power of two");
}
}
 
fred rosenberger
lowercase baba
Bartender
Posts: 12562
49
Chrome Java Linux
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Govind SrinivasaRaghavan:


try this. it prints "The number is a power of two"
[ April 15, 2008: Message edited by: Fred Rosenberger ]
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
yup i m sorry...that was a mistake...
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Again, please don't just give out answers like that. HHD has plenty of hints, and needs to try writing some code for practice.
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sorry for posting the answer guys...i thought i would help someone out

Sorry Fred and Jim...But I guess it can help them think

the answer uses bitwise and operator and is just one line

if((x & (x-1)) == 0) return true else return false

Hope this helps you...All the best for your interview
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Sigh.

I'm tempted to delete that, but since it still has a couple defects, I suppose it can serve as fodder for further discussion. One defect will be obvious to any compiler, and is easily fixed. The other is more subtle...
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
oh...i just compiled that and it seemed to run perfectly fine....just wondering what the error is...Will be glad to rectify it
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
No, you compiled something very similar to what you posted. Copying and pasting the code into an IDE (or just using javac) will make the problem more obvious.

As for the subtle error: are you sure this works for all possible inputs?
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
i got the error that you were talking about. it was probably the brackets surrounding the variable x that you must have mentioned...Sorry i typed it wrongly here....

As for integer inputs, I even tried inputs of both extremes....ie Integer.MIN_VALUE and Integer.MAX_VALUE and i got the desired results.... I would be glad to know if there are any input cases for which the logic fails
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I do see something very similar to what I found when I Googled for it. I preferred to go for a recursive solution, but I am keeping quiet about what it is, at least for the time being. I can get my solution into a single, rather long, line.
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[GSR]: i got the error that you were talking about. it was probably the brackets surrounding the variable x that you must have mentioned...Sorry i typed it wrongly here....

Well, no. It's a basic syntax issue though.

[GSR]: As for integer inputs, I even tried inputs of both extremes....ie Integer.MIN_VALUE and Integer.MAX_VALUE and i got the desired results....

Um, that's very strange, since Integer.MIN_VALUE is one of two numbers that works incorrectly when I test it. Do you think Integer.MIN_VALUE is a power of two, or not? What does the method tell you?

There is another input value which yields incorrect results. It's another extreme, sort of.

The good news is that it's possible to fix these problems and still get a solution which is approximately the same speed as the fastest solution I had come up with on my own. So this solution can be both fast and short. Now it just needs to be correct.
[ April 15, 2008: Message edited by: Jim Yingst ]
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
I would have thought MIN_VALUE is the last value to be a power of 2.
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ooooooooooooh!

It does give the wrong answer for Integer.MIN_VALUE.
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
with integer.MIN_VALUE...my method does return true....and i got what you are talking about....I guess the problem with Integer.MIN_VALUE is probably because of the sign bit set as 1. And what was the other input that you are talking about
 
Hari Srinivas
Ranch Hand
Posts: 46
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Yeah guys...figured it out anyway...and I still don't think that we need to use any loop as requested by Mr Hdd... And I think everybody else except him are trying to work on a solution!

And Campbell I guess you were initially thinking in the lines of using shift operators...were you...I thought you said you were looking at a recursive solution
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Shift operators? Recursion?

I've got both!
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Right, cards on the table please.

HHD: show us what you've got, never mind how well or badly it works.
 
Rodrigo Lopes
Ranch Hand
Posts: 119
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ok, congratulations, you guys know everything about shift and bitwise operations.
Nobody said anything that the code had to be the fastest or the smallest.
What about maintenance? Wouldn't it be better if the code could be clear to anyone that reads it?
 
Vikas Kapoor
Ranch Hand
Posts: 1374
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Originally posted by Campbell Ritchie:
HHD: show us what you've got, never mind how well or badly it works.


He is afraid that you start pulling his leg also.
 
Gavin Tranter
Ranch Hand
Posts: 333
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Hi R Lopes, considering it was an interview question, I think the interviews would have wanted the most efficent answer, using a bitwise &.

Also, I personal feel in this case that the bitwise & is the most readable and maintainable, and because it is not a commonly used operator in Java I would add a comment (you know those things that aid in maintanablity of code) describing the algorithmn and that I am using a bitwise &.
I would also put it in its own method, with a descriptive name, something like isPowerOfTwo(long value).

Not sure how to get mine to work for negatives though, actual I am not even sure what the negative powers of 2 are.

[ April 16, 2008: Message edited by: Gavin Tranter ]
[ April 16, 2008: Message edited by: Gavin Tranter ]
 
Campbell Ritchie
Marshal
Posts: 56518
172
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
The negative arguments cannot be parsed; they are never powers of a positive number.
The negative powers are fractions, eg 2^-1 = � 2^-2 = �, so we are only interested in positive numbers and positive powers if we are using ints.
 
Gavin Tranter
Ranch Hand
Posts: 333
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
Ah. Thanks, I didnt know that.
The method I have handles that as it returns false for negatives, except MIN_VALUE, which I should have spotted cos I was just talking about MIN_VALUE and MAX_VALUE yesterday! DOH!!!.

Zero also returns true. :S

[ April 16, 2008: Message edited by: Gavin Tranter ]
[ April 16, 2008: Message edited by: Gavin Tranter ]
 
Jim Yingst
Wanderer
Sheriff
Posts: 18671
  • Mark post as helpful
  • send pies
  • Quote
  • Report post to moderator
[R Lopes]: Nobody said anything that the code had to be the fastest or the smallest.
What about maintenance? Wouldn't it be better if the code could be clear to anyone that reads it?


Several people did say something about that - Gavin and myself, for example. We were quite clear about it. The interviewer didn't say that, but that doesn't mean he's not interested. Really, in an interview I'd probably just ask them if they were more interested in speed or simplicity. Show them you're aware of the tradeoffs that can be involved, and give them options.

Having said that, I don't know if the code has to be immediately clear to anyone who reads it. The n & (n - 1) trick isn't immediately obvious, but the fact that it's so short makes it very easy to maintain once you understand it. As Gavin said, if you put it in its own method with a nice clear descriptive name, the intent of the code is pretty obvious. The details of how it works may not be quite as immediately obvious, but And since it's also very fast, I think it would be an excellent answer. Except for:

[Gavin]: considering it was an interview question, I think the interviews would have wanted the most efficent answer, using a bitwise &.

Well, considering the original question said to use a while loop, I think the interviewer wanted a while loop, at least for the initial answer. Really, that seems like a pretty silly requirement, but OK.

It's possible to use bitwise operators as part of a while loop. For example:

This is similar to earlier while loop answers, but slightly faster. Not as fast as using either n & (n -1) or a switch statement, but if the interviewer wants a loop, give them a loop.

On the other hand, we've also extended this discussion beyond the original question. Personally I think that there are several other answers that are better than using a while loop, which we've been discussing. They're just not answers to the original question.

[Gavin]: Zero also returns true. :S

Yup, that's the other value I was referring to. Good values to test on any function that takes an integer include 0, 1, 2, MAX_VALUE, -1, MIN_VALUE. Other values may well be significant, depending on the problem, but those are usually good starting points to consider.

The n & (n - 1) answer can be modified with a simple condition to exclude both 0 and MIN_VALUE:


The other answer I like is this:

Sure, it's long, but it's pretty simple, and it's about the same speed as the n & (n - 1) solution. Nowadays its unusual to see switch statements used, but sometimes they work quite well. I like n & (n - 1) better, but if you don't notice that possibility (as I didn't, initially) this is a good alternate.
 
It is sorta covered in the JavaRanch Style Guide.
  • Post Reply Bookmark Topic Watch Topic
  • New Topic
Boost this thread!