Code: Select all
static int bitCount(int a){int b=0;while(a>0){a&=a-1;b++;}return b;}
Moderators: phlip, Moderators General, Prelates
Code: Select all
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.
Code: Select all
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.
Code: Select all
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;
}
Code: Select all
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.
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
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}).
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
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
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.
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
Sc4Freak wrote:Without looking at the source I have no idea how it works.
Code: Select all
#!/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
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Thesh wrote:For counting 1 bits (hamming weight), see:
http://graphics.stanford.edu/~seander/b ... etParallelCode: 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
Code: Select all
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];
Code: Select all
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);
Code: Select all
c = (v & 0x55555555) + ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0xf0f0f0f) + ((c >> 4) & 0xf0f0f0f);
c = (c * 0x1010101) >> 24;
Code: Select all
c = v - ((v >> 1) & 0x55555555);
c = (c & 0x33333333) + ((c >> 2) & 0x33333333);
c = (c & 0xf0f0f0f) + ((c >> 4) & 0xf0f0f0f);
c = (c * 0x1010101) >> 24;
Code: Select all
/* 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.
a = a^b
b = a^b
a = a^b
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Code: Select all
a ^= b;
b ^= a;
a ^= b;
Code: Select all
a, b = b, a
Lol! And if it's possible to seem simple, then it was fucking hard to write.If it was hard to write, it should be hard to figure out.
That tells me how long its been since I've c'ed.PM 2Ring wrote:If that's C, you're missing a few semicolons.
Code: Select all
a ^= b ^= a ^=b;
I'd say that its definitely in the too clever basket, but its interesting that its possible. Most people will tell you you can't swap variables without a temp. You can, its just at the cost of three arithmetic operations compared with freeing a single register (a move to cache and back at worst). You can use this sort of trick to make a doubly linked list with just a single pointer at each node: make that pointer the xor of the next and prev and keep two pointers to tell you where you are, a here and a next. Again, its doable, but its very much in the "too clever" basket.PM 2Ring wrote:I suppose some people would consider it too clever and prefer to use an explicit temporary variable. But I guess it could come in handy for tiny embedded systems where every byte counts.
Quasi interestingly, I originally saw the possibility for this using integers and arithmetic: a +=b; b-=a; a-=b. Its only necessary to use xors for non arithmetic types and floats (you'll lose precision doing this with most floats).PM 2Ring wrote:If you use that construction in Python where one of a & b is an int but the other is long, they'll both end up as long after the swap.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Nasal demons.jestingrabbit wrote:Even more reduced (I believe this should work, but haven't checked).Code: Select all
a ^= b ^= a ^=b;
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
jestingrabbit wrote:That tells me how long its been since I've c'ed.PM 2Ring wrote:If that's C, you're missing a few semicolons.
Even more reduced (I believe this should work, but haven't checked).Code: Select all
a ^= b ^= a ^=b;
Code: Select all
a = a^b, b = a^b, a = a^b;
jestingrabbit wrote:I'd say that its definitely in the too clever basket, but its interesting that its possible. Most people will tell you you can't swap variables without a temp. You can, its just at the cost of three arithmetic operations compared with freeing a single register (a move to cache and back at worst). You can use this sort of trick to make a doubly linked list with just a single pointer at each node: make that pointer the xor of the next and prev and keep two pointers to tell you where you are, a here and a next. Again, its doable, but its very much in the "too clever" basket.PM 2Ring wrote:I suppose some people would consider it too clever and prefer to use an explicit temporary variable. But I guess it could come in handy for tiny embedded systems where every byte counts.
jestingrabbit wrote:Quasi interestingly, I originally saw the possibility for this using integers and arithmetic: a +=b; b-=a; a-=b. Its only necessary to use xors for non arithmetic types and floats (you'll lose precision doing this with most floats).PM 2Ring wrote:If you use that construction in Python where one of a & b is an int but the other is long, they'll both end up as long after the swap.
All I really assume is that the two things, a and b, have the same number of bits in their representation and that we have the xor act in a bitwise manner, in which the bits paired in the operation a^b are the same as those paired in b^a. Its interesting that not even C guarantees these things for pointers, but the idea in a case like that would be to cast to some sort of "bag of bits" type, like python 3's "bytes".PM 2Ring wrote:Doing any arithmetic on pointers apart from addition / subtraction invokes undefined behaviour, IIRC. Sure, pointers are integers on sane architectures, however not all architectures are sane.
PM 2Ring wrote:jestingrabbit wrote:Quasi interestingly, I originally saw the possibility for this using integers and arithmetic: a +=b; b-=a; a-=b. Its only necessary to use xors for non arithmetic types and floats (you'll lose precision doing this with most floats).PM 2Ring wrote:If you use that construction in Python where one of a & b is an int but the other is long, they'll both end up as long after the swap.
Doing it with addition and subtraction may not work properly, due to overflow. I guess it'd work on unsigned types but I couldn't be bothered checking ATM `cause it's too darned hot.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.
Code: Select all
factor = [""]*1000000
n = 2
while n < len(factor):
if factor[n] == "":
factor[n] = str(n)
for i in range(2,int((len(factor)-1)/n)+1):
factor[i*n] = factor[i] +"*" +str(n)
n+=1
Flumble wrote:I do have to disqualify that one: it only lists the unique prime divisors, not their multiplicity. 12≠2*3.
...unless I've misread the code, in which case you should kill me now.
Flumble wrote:(and you've got a few code'os, namely [...] int((len(factor)-1)/n)+1; the -1 is correct if int is the ceiling function )
Code: Select all
for i in range(2*n, len(factor), n):
factor[i] = factor[i//n] + "*" + str(n)
Code: Select all
enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};
void ┻━┻︵╰(ಠ_ಠ ⚠) {exit((int)⚠);}
Users browsing this forum: No registered users and 12 guests