http://www.perlmonks.org?node_id=582361


in reply to Re^4: Powerset short-circuit optimization
in thread Powerset short-circuit optimization

Hi, L~R...

First the good news: the algorithm seems fine to me, and there's only one language-specific gotcha I found that could have caused you problems. That's very impressive for someone with next-to-no C experience.

Now the critique: This is hard code to review. The explanation helps, but there are a lot of things that get in the way.

With all those impediments, the only way this ordinary human was able to get through that and follow it from start to finish was to rewrite it myself. In so doing, I'm happy to report the only thing I found that was really off was this:

memset(seen, '0', sizeof(seen)); /* ... snip ... */ if (seen[bit] == '1') { return; } seen[bit] = '1';

In C, '0' != 0 and '1' != 1. Those single quotes return the integer value of the enclosed character, which, for '0' on an ascii machine is not 0 but 48. :) You got away with it because you were consistent, though. :) That memset() should look like this:

memset(seen, 0, sizeof(seen));
--
Marvin Humphrey
Rectangular Research ― http://www.rectangular.com