- Code: Select all
static int bitCount(int a){int b=0;while(a>0){a&=a-1;b++;}return b;}
Moderators: phlip, Prelates, Moderators General
static int bitCount(int a){int b=0;while(a>0){a&=a-1;b++;}return b;}
snow5379 wrote:Have you ever seen an algorithm that just blew your mind and made you wonder how it was ever thought of? For example I find the following one amazing:
- Code: Select all
static int bitCount(int a){int b=0;while(a>0){a&=a-1;b++;}return b;}
troyp wrote:snow5379 wrote:Have you ever seen an algorithm that just blew your mind and made you wonder how it was ever thought of? For example I find the following one amazing:
- Code: Select all
static int bitCount(int a){int b=0;while(a>0){a&=a-1;b++;}return b;}
I'm sorry, I have to ask: can you think of a *more* obvious and straightforward way to count the number of bits in a int than the one you quoted? Because personally, I would find *that* amazing.
b = 0;
while (a > 0) {
if (a & 1) {
b++;
}
a = a >> 1;
}
troyp wrote:I'm sorry, I have to ask: can you think of a *more* obvious and straightforward way to count the number of bits in a int than the one you quoted? Because personally, I would find *that* amazing.
while( a > 0 ){
/* add one if a is odd, add zero otherwise */
b += ( a & 1 );
/* divide a by 2 */
a >>= 1;
}
scarecrovv wrote:Well the most obvious and straightforward way is...
You've got to admit that the a&=a-1 optimization is clever.
shawnhcorey wrote:troyp wrote:I'm sorry, I have to ask: can you think of a *more* obvious and straightforward way to count the number of bits in a int than the one you quoted? Because personally, I would find *that* amazing.
- Code: Select all
while( a > 0 ){
/* add one if a is odd, add zero otherwise */
b += ( a & 1 );
/* divide a by 2 */
a >>= 1;
}
for (b = 0; a; a >>= 1) b += (a & 1);
Proginoskes wrote:shawnhcorey wrote:troyp wrote:I'm sorry, I have to ask: can you think of a *more* obvious and straightforward way to count the number of bits in a int than the one you quoted? Because personally, I would find *that* amazing.
- Code: Select all
while( a > 0 ){
/* add one if a is odd, add zero otherwise */
b += ( a & 1 );
/* divide a by 2 */
a >>= 1;
}
You forgot to initialize. Also, a for loop makes it one statement long:
- Code: Select all
for (b = 0; a; a >>= 1) b += (a & 1);
letterX wrote:Why are your comments helpful?
shawnhcorey wrote:letterX wrote:Why are your comments helpful?
Documentation is like sex: when it's good, it's very, very good; and when it's bad, it's still better than nothing.
-- Dick Brandon
shawnhcorey wrote:You forgot the comments.
Proginoskes wrote:Getting back to the original topic ... There is a polynomial-time (cubic, even) algorithm which checks to see whether a graph G can be embedded in 3-dimensional space with every cycle being (homeomorphic to) the unknot. (This is due to a series of papers about graph minors published by Robertson and Seymour; you just check to see whether G has a "minor" isomorphic to a graph in a certain finite set S.) However, no one knows any algorithm for this task, even a double-exponential one!
This has to be a mind-blowing result, if anything.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
WarDaft wrote:Proginoskes wrote:Getting back to the original topic ... There is a polynomial-time (cubic, even) algorithm which checks to see whether a graph G can be embedded in 3-dimensional space with every cycle being (homeomorphic to) the unknot. (This is due to a series of papers about graph minors published by Robertson and Seymour; you just check to see whether G has a "minor" isomorphic to a graph in a certain finite set S.) However, no one knows any algorithm for this task, even a double-exponential one!
This has to be a mind-blowing result, if anything.
See, this is probably the sort of thing we'd get even if we did find P=NP.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
phlip wrote:Well, there exists a meta-algorithm that can solve any NP problem, which has the property that if P=NP then it will run in polynomial time.
It just has an absolutely ridiculous constant term and is in no way usable in the real world (essentially, if the shortest program that could solve the problem in polynomial time is n bits long, then the meta-algorithm will solve the problem in polynomial time with a constant term on the order of 4^{n}).
for n in [1..]:
for i in [1..n]:
Simulate Turing machine i, with input inp, for n steps
ans := the result of the simulated Turing machine
if F(inp. ans) returns true:
return ans
phlip wrote:Wikipedia covers the basics, but it's pretty simple. First you need some sort of enumeration of all the possible Turing machines, so that you can say "run Turing machine number 17 for 30 steps" and see what you get. Then, given F(inp, ans) which returns true if ans is the correct answer for the input inp for a particular NP puzzle (by definition, there is code to calculate F() in polynomial time... that's what NP means). Then, you can do this:Now, if Turing machine i solves the problem, and it takes n steps, then this will take on the order of max(i^{2}, n^{2}) loops to find, and each loop will run the F() function, which is polynomial-time.
- Code: Select all
for n in [1..]:
for i in [1..n]:
Simulate Turing machine i, with input inp, for n steps
ans := the result of the simulated Turing machine
if F(inp. ans) returns true:
return ans
So the end result is that, if Turing machine i solves the problem in O(f(n)) time, and our checker-function can check a solution in O(g(n)) time, then this meta-algorithm will accept the problem in O(max(i^{2}, f(n)^{2}) * g(n)) time. All the terms there are polynomial in terms of n (i^{2} is a constant for a given problem in terms of n, g(n) is polynomial by definition, f(n) is polynomial if P=NP). So the full expansion is also a polynomial (it's one polynomial, squared, times another polynomial). But i^{2} is the constant term, and it's very big (if the program found is k bits long, then i=2^{k}, so the constant term is i^{2}=4^{k}).
Now, if P != NP, then this meta-algorithm will still work the same... but it won't necessarily find a polynomial-time solution to simulate (indeed, for an NP-complete problem, it won't find one), so the runtime of the meta-algorithm will blow out and won't be polynomial either. However, the meta-algorithm will always work if there exists a machine that will solve the problem, and it's been proven that every NP problem can be solved in exponential time with a brute-force search. So it all else fails, the meta-algorithm will find a Turing machine that does that brute-force search, which will in turn eventually find the solution.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
letterX wrote:It's also worth pointing out that on inputs that should return "no", the algorithm runs forever (note that there isn't any mechanism for the program even ouputting "no"). So it's only a polynomial-time recognizer for an NP-complete language, not a full algorithm. I don't actually know of an algorithm which is guaranteed to halt in p(n) steps for some polynomial, assuming P=NP, but it's possible that there is one that I don't know about.
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
Sc4Freak wrote:Without looking at the source I have no idea how it works.
#!/usr/bin/python
def next_permutation(lst):
tail_size = 1
while lst[-tail_size-1] >= lst[-tail_size]:
tail_size += 1
if tail_size >= len(lst):
return lst[::-1]
a = lst[-tail_size-1]
for i in xrange(1,tail_size+1):
if lst[-i] > a:
break
return lst[:-tail_size-1] + [lst[-i]] + lst[len(lst)-i+1:][::-1] + [lst[-tail_size-1]] + lst[-tail_size:-i][::-1]
def tst(a, n):
print a
for i in xrange(n):
a = next_permutation(a)
print a
tst([1,2,3,4], 24) # simple permutations
print "====="
tst([1,2,2,3], 12) # permutations with repeated elements
print "====="
class A:
def __init__(self,a,b):
self.a = a
self.b = b
def __str__(self):
return "A(%s,%s)" % (self.a, self.b)
__repr__ = __str__
def __cmp__(self, other):
return self.a.__cmp__(other.a)
tst([A(1,1), A(2,1), A(2,2), A(3,1)], 12) # permutations with repeated but distinct elements for tracking
Thesh wrote:For counting 1 bits (hamming weight), see:
http://graphics.stanford.edu/~seander/b ... etParallel
- Code: Select all
v = v - ((v >> 1) & 0x55555555); // reuse input as temporary
v = (v & 0x33333333) + ((v >> 2) & 0x33333333); // temp
c = ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24; // count
unsigned int v; // count bits set in this (32-bit value)
unsigned int c; // store the total here
static const int S[] = {1, 2, 4, 8, 16}; // Magic Binary Numbers
static const int B[] = {0x55555555, 0x33333333, 0x0F0F0F0F, 0x00FF00FF, 0x0000FFFF};
c = v - ((v >> 1) & B[0]);
c = ((c >> S[1]) & B[1]) + (c & B[1]);
c = ((c >> S[2]) + c) & B[2];
c = ((c >> S[3]) + c) & B[3];
c = ((c >> S[4]) + c) & B[4];
c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0xf0f0f0f) + ((c >> 4) & 0xf0f0f0f);
c = (c & 0xff00ff) + ((c >> 8) & 0xff00ff);
c = (c & 0xffff) + ((c >> 16) & 0xffff);
c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0xf0f0f0f) + ((c >> 4) & 0xf0f0f0f);
c = (c * 0x1010101) >> 24;
c = v - ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0xf0f0f0f) + ((c >> 4) & 0xf0f0f0f);
c = (c * 0x1010101) >> 24;
/* count number of 1's in 9-bit argument (Schroeppel) */
unsigned count_ones(unsigned36 a) {
return ((a * 01001001001) /* 4 adjacent copies */
& 042104210421) /* every 4th bit */
% 15; /* casting out 15.'s in hexadecimal */
}
phlip wrote:Well, there exists a meta-algorithm that can solve any NP problem, which has the property that if P=NP then it will run in polynomial time.
It just has an absolutely ridiculous constant term and is in no way usable in the real world (essentially, if the shortest program that could solve the problem in polynomial time is n bits long, then the meta-algorithm will solve the problem in polynomial time with a constant term on the order of 4^{n}).
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.
Users browsing this forum: No registered users and 3 guests