|
Hi,
it is much simpler than that.
one spec is missing: what if input is zero ?
THEORY (assume unsigned integers)
1.
if all zeroes followed by all ones, then one more becomes a power of two
2.
if all ones followed by all zeroes, then bitwise complement reverts to first case
3.
a power of two has just one bit set; it can be tested in one line:
if (( x & (-x) )==x) then either x = zero or x = power of 2 !!!
CODE
if (x==0) return whatever you think is appropriate
if ((x&(-x))==x) return 1;
x=~x;
if ((x&(-x)==x) return 2;
return 3;
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
You won
Russell
|
|
|
|
|
I knew there would be a clever bit twiddling answer to this - very neat!
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
fn(WORD w)
{
WORD mark=0x8000;
if(w&mark)
{
mark >>= 1;
while( (w&mark) && mark )
mark >>= 1;
if(mark==0)//w must = 0xffff,return 1 or 2
return 2;//also can return 1
if(w&(mark-1))
return 0;
else
return 2;
}
else
{
mark >>= 1;
while( ((w&mark)==0) && mark )
mark >>= 1;
if( (w&(mark-1))==(mark-1) )
return 1;
else
return 0;
}
}
|
|
|
|
|
Hi,
what about...
int GetWordStatus(int word,int word length)
{
if (word == 0)
return 0;
int nHigh = word / pow (2, word_length);
int nLow = word % pow (2, word_length);
if (nHigh > nLow)
return 1;
else if (nHigh < nLow)
return 2;
else
return 3;
}
Greetings.
--------
M.D.V.
If something has a solution... Why do we have to worry about?. If it has no solution... For what reason do we have to worry about?
Help me to understand what I'm saying, and I'll explain it better to you
|
|
|
|
|
There are two sets
one set has ten thousands elements
other set has 30 element
Which loop would be the faster
for(i = 0; i < sizeoffirstset(10000); i++)
{
for (j=0; i < sizeofsecondset(20); j++)
{
if(set1[i] == set2[j])
//do some thing
}
}
for(i = 0; i < sizeofsecondset(20); i++)
{
for (j=0; i < sizeoffirstset(10000); j++)
{
if(set2[i] == set1[j])
//do some thing
}
}
Best Regards,
Mushq
Mushtaque Ahmed Nizamani
Software Engineer
Ultimus Pakistan
|
|
|
|
|
Both are doing the same operations, just in a different order.
|
|
|
|
|
Mushq wrote: sizeofsecondset(20)...sizeoffirstset(10000)
const UINT Sizeoffirstset =sizeoffirstset (10000);
const UINT Sizeofsecondset=sizeofsecondset(20);
for(i = 0; i < Sizeofsecondset; i++)
{
for (j=0; j < Sizeoffirstset; j++)
{
if(set2[i] == set1[j])
}
}
I'm looking for differences, I see only that the initialization j=0 is computed Sizeofsecondset times ... so let Sizeofsecondset be the smaller number.
Russell
|
|
|
|
|
Mushq wrote: for(i = 0; i < sizeoffirstset(10000); i++)
{
for (j=0; i < sizeofsecondset(20); j++)
Ahahah
faster yes .... but to go where?
Russell
|
|
|
|
|
First one is faster and because of internal smaller array.
run following code in VB:
Dim i, j As Integer
Dim strArr1(10000) As String
Dim strArr2(20) As String
For i = 0 To 10000
strArr1(i) = i & ""
Next
For i = 0 To 20
strArr2(i) = i * i * i & ""
Next
Response.Write(DateTime.Now.Millisecond.ToString())
For i = 0 To 10000
For j = 0 To 20
If (strArr1(i) = strArr2(j)) Then
Response.Write("
Hello" & strArr1(i) & strArr2(j))
End If
Next
Next
Response.Write(DateTime.Now.Millisecond.ToString())
For i = 0 To 20
For j = 0 To 10000
If (strArr2(i) = strArr1(j)) Then
Response.Write("
Hello " & strArr2(i) & strArr1(j))
End If
Next
Next
Response.Write(DateTime.Now.Millisecond.ToString())
Any systematic work reflects its significance for a long time. So let's discuss the best...
|
|
|
|
|
Yes: finally the best way to find out who is the faster is use ... the clock
Russell
|
|
|
|
|
Sure, measuring is good, smart measuring is even better.
if you have two alternatives that are likely to be almost equal, whichever you try first
will take longer, due to different starting conditions (maybe code needs to be JITted,
probably data needs to be loaded in memory and/or will be loaded in cache, etc).
Remedy: put everything in a for loop, and run a few passes; ignore the first pass,
take the average (or the best time!) of the remaining passes.
Luc Pattyn [Forum Guidelines] [My Articles]
this weeks tips:
- make Visual display line numbers: Tools/Options/TextEditor/...
- show exceptions with ToString() to see all information
- before you ask a question here, search CodeProject, then Google
|
|
|
|
|
Thanks for reply.
rihdus wrote: First one is faster and because of internal smaller array.
can you please explain a bit more.
Best Regards,
Mushq
Mushtaque Ahmed Nizamani
Software Engineer
Ultimus Pakistan
|
|
|
|
|
clock_t start,end;
start=clock();
//your code snippet here
end=clock();
//observe start=end here.
hope you got the point.
|
|
|
|
|
If time is important you could almost certainly do better than either way. For example, instead doing a simple search 10000 times on a set of 20 things, spend a bit of time and either order them or hash them, so that the search that you have to do many times is much faster.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
Mushq wrote: for(i = 0; i < sizeoffirstset(10000); i++)
{
for (j=0; i < sizeofsecondset(20); j++)
{
if(set1[i] == set2[j])
//do some thing
}
}
another optimization:
for(i = 0; i < sizeoffirstset(10000); i++)
{
const double set1_i_ = set1[i];
for (j=0; j < sizeofsecondset(20); j++)
{
if(set1_i_ == set2[j])
}
}
In this way the program not needs to reload that value every time loooking into the array.
Hoping that the compiler is enough smart to better solution itself.
You can only check the time spend in every solutions and see who is the faster...
Important: do this time check in Release mode!!!
also look to the project features...I remember that there is some flags like smallest exe file dimension vs fastest run exe (that somethimes can be bigger)....but I don't remember the name of this flags.
Hope helps
Russell
|
|
|
|
|
_Russell_ wrote: Important: do this time check in Release mode!!!
Could you please explain a bit what the difference is?
Thanks.
|
|
|
|
|
The difference is that in DEBUG mode the code is compiled exactly as you write it and it isn't optimizated. For example, inline functions are not inline and macros like ASSERT are inserted in the application.
In RELEASE mode the code is optimized: inline functions will become inlined and ASSERTs are cutted from the code.
In this case the code is really faster and it does exactly what you want, without do any internal test.
Of course you have, first, to prepare the routines in DEBUG mode, to be sure that there isn't errors, but when you take the clock in your hand to see what algorithm is faster... then use the RELEASE mode.
You can find details on the differences between DEBUG mode and RELEASE mode into the documentation.
Russell
|
|
|
|
|
Both are same because the no. of iterations is same.
Best Regards,
Chetan Patel
|
|
|
|
|
1. A partition of a positive integer n is a sequence of positive integers that sum to n. Write an algorithm in psedocode and then implement the algorithm (in C) to print all non-increasing partitions of n.
eg. If n=4
4
3 1
2 2
2 1 1
1 1 1 1
|
|
|
|
|
convince me it's not homework!
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
thank you , however at the moment i'm expecting suport
|
|
|
|
|
The best support and advice I can offer you is to try to tackle the question yourself. By struggling with problems, you develop problem solving skills, the solutions you discover or don't discover yourself are far more important than those you read here. Had you thought about this problem and had that flash of inspiration to use recursion, apart from the self-satisfaction it brings - you would probably have remembered it for a long time. Conversely, the elegance of the recursive approach would be blinding if you had spent a long time trying to solve it some other way.
Tip: If you are going to post your homework questions, at least remove the question number - it makes it too easy to spot.
Peter
"Until the invention of the computer, the machine gun was the device that enabled humans to make the most mistakes in the smallest amount of time."
|
|
|
|
|
|
cp9876 wrote: at least remove the question number - it makes it too easy to spot
 And that was only the first problem, too. 
"Any sort of work in VB6 is bound to provide several WTF moments." - Christian Graus
|
|
|
|
General 
News 
Suggestion 
Question 
Bug 
Answer 
Joke 
Praise 
Rant 
Admin 
Submit an article or tip
