@Gaurav: Even though this is O(log n), it is bound to be slow, since
it would use division and modulus are among the slowest operations on
modern computers, some of which don't even have an integer division
instruction. Here is a revision to my earlier code, for 32-bit
integers. It should be faster since it contains no loops.
bool PowerOfThree(unsigned int n)
{
int powsof3[32] =
{1,3,0,9,27,0,81,243,0,729,0,2187,6561,0,19683,59049,0,
177147,0,531441,1594
323,0,4782969,14348907,0,43046721,
129140163,0,387420489,0,1162261467,3486784401};
int i = if( n >> 16 ) ? 16 : 0;
if( n >> (i+8) ) i += 8;
if( n >> (i+4) ) i += 4;
if( n >> (i+2) ) i += 2;
if( n >= (i+1) ) i += 1;
return powsof3[i] == n;
}
As in the previous algorithm, the first few statements use a binary
search to find the bit number of the highest order bit set. There can
be at most one power of three corresponding to each high-order-bit
number, so we then check to see if the input number is the only
possible power of three in the table of powers of 3 that is indexed by
the high-order-bit number. The zeros in powsof3[] correspond to high-
order-bit numbers that have no power of three.
Dave
On Dec 9, 2:35 am, Gaurav Kumar <[email protected]> wrote:
> What if we create a base 3 number from the given number N and then check if
> there is only 1 bit with value 1 and all values should be 0. For example, if
> lets say the number is 27. Its base 3 number will be 1 0 0 0, now since there
> is only 1 single 1 present in this representation, it is a power of 3.
>
> Gaurav
>
> On Dec 7, 2011, at 6:03 PM, saurabh singh wrote:
>
>
>
> > Originaly problem rules out the use of log.Moreover log (or any floating
> > point operations) take lot of hardware time as they are emulated on the
> > floating point environment on most machines.Thirdly precision problem for
> > higher values of n may cause your solution to give wron g answers,,,
>
> > On Wed, Dec 7, 2011 at 11:54 PM, tech coder <[email protected]>
> > wrote:
> > what about this log(base 3 n) is of integral type then n is a power of 3
>
> > On Mon, Dec 5, 2011 at 11:36 PM, Dave <[email protected]> wrote:
> > @Carl: You can generate the constants the first time the procedure is
> > called. There is no need to do them every time. So the first call
> > would be O(wordsize) but subsequent calls are O(1).
>
> > Dave
>
> > On Dec 5, 10:28 am, Carl Barton <[email protected]> wrote:
> > > Sorry, I was being a bit vague. I meant what would the time complexity be
> > > then?
> > > As I understand your Constant time is Dependant on the constant pre
> > > computation you do, which is no longer the case when you generalise
>
> > > On 5 December 2011 16:14, Dave <[email protected]> wrote:
>
> > > > @Carl: Of course. For any given word size, extend the tables of powers
> > > > of 2 and of 3 and change the for loop limit.
>
> > > > Dave
>
> > > > On Dec 5, 9:36 am, Carl Barton <[email protected]> wrote:
> > > > > Ah I see, in which case could you not generalise your solution for all
> > > > > integers?
> > > > > By taking into account the size of words on the computer for example?
>
> > > > > On 5 December 2011 15:09, Dave <[email protected]> wrote:
>
> > > > > > @Carl: Yes, as coded, my algorithm is for 32-bit integers. But the
> > > > > > original poster asked for a solution using bit manipulation, and
> > > > > > modulus and division are arithmetic operations, not bit operations.
>
> > > > > > Dave
>
> > > > > > On Dec 5, 8:56 am, Carl Barton <[email protected]> wrote:
> > > > > > > @Dave Yours only works for a certain subset of all possible powers
> > > > or 3
> > > > > > > doesn't it? So WgpShashank's would be more general?
>
> > > > > > > On 5 December 2011 14:30, Dave <[email protected]> wrote:
>
> > > > > > > > @WgpShashank: Yours is an O(log n) solution. Mine is O(1).
>
> > > > > > > > Dave
>
> > > > > > > > On Dec 5, 6:21 am, WgpShashank <[email protected]>
> > > > > > > > wrote:
> > > > > > > > > @SAMMM have a look
>
> > > > > > > > > * *solution is to keep dividing the number by 3, i.e, do n =
> > > > > > > > > n/3
> > > > > > > > > iteratively. In any iteration, if n%3 becomes non-zero and n
> > > > > > > > > is
> > > > not 1
> > > > > > > > then
> > > > > > > > > n is not a power of 3, otherwise n is a power of 3
>
> > > > > > > > > check it out ?http://codepad.org/863ptoBE
>
> > > > > > > > > Thanks
> > > > > > > > > Shashank
> > > > > > > > > Computer Science
> > > > > > > > > BIT Mesrahttp://
> > > > > > > >www.facebook.com/wgpshashankhttp://shashank7s.blogspot.com/
>
> > > > > > > > --
> > > > > > > > You received this message because you are subscribed to the
> > > > > > > > Google
> > > > > > Groups
> > > > > > > > "Algorithm Geeks" group.
> > > > > > > > To post to this group, send email to [email protected].
> > > > > > > > To unsubscribe from this group, send email to
> > > > > > > > [email protected].
> > > > > > > > For more options, visit this group at
> > > > > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > > > > --
> > > > > > You received this message because you are subscribed to the Google
> > > > Groups
> > > > > > "Algorithm Geeks" group.
> > > > > > To post to this group, send email to [email protected].
> > > > > > To unsubscribe from this group, send email to
> > > > > > [email protected].
> > > > > > For more options, visit this group at
> > > > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > > > --
> > > > You received this message because you are subscribed to the Google
> > > > Groups
> > > > "Algorithm Geeks" group.
> > > > To post to this group, send email to [email protected].
> > > > To unsubscribe from this group, send email to
> > > > [email protected].
> > > > For more options, visit this group at
> > > >http://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group
> > athttp://groups.google.com/group/algogeeks?hl=en.
>
> > --
>
> > Regards
> > "The Coder"
>
> > "Life is a Game. The more u play, the more u win, the more u win , the more
> > successfully u play"
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group
> > athttp://groups.google.com/group/algogeeks?hl=en.
>
> > --
> > Saurabh Singh
> > B.Tech (Computer Science)
> > MNNIT ALLAHABAD
>
> > --
> > You received this message because you are subscribed to the Google Groups
> > "Algorithm Geeks" group.
> > To post to this group, send email to [email protected].
> > To unsubscribe from this group, send email to
> > [email protected].
> > For more options, visit this group
> > athttp://groups.google.com/group/algogeeks?hl=en.
--
You received this message because you are subscribed to the Google Groups
"Algorithm Geeks" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/algogeeks?hl=en.
