On Sat, Apr 10, 2010 at 09:53:42PM -0500, Andrei Alexandrescu wrote: > Ha! Good point. I'd forgotten the initial requirement and considered > both values to start at 0. They don't! Adam? :o)
Yeah, my big brute-force tester program ran loops for min_a and min_b too. And it tripped an assert. core.exception.asserter...@or.d(60): [10, 10]. expected: 3, got 2 (min == 2) I hacked it by only asserting if the mins are zero too... but I did mention it a couple of times in my spam as the day has gone on. I'm going to lecture a bit in this post. It is mostly for my benefit - maybe if I write up the patterns and thoughts explicitly, something new will come to mind. My current solution uses a pattern I noticed: 0100 1000 There, the best you get is 1100. But, 0100 1100 Lets you get to 1111. The reason is that duplicated one in there means you can trade a 100 for a 011, and still OR in the 100 thanks to the duplicate. So, I take the two numbers and OR them together, but then, if there is a bit duplicated, I trade one of them for all the following ones, and or that in too. That leads to the one liner solution: return a | ((1 << numbits(a&b)) - 1) | b; We OR the two values, then use AND to find duplicated bits. We take the biggest one and trade it out (a power of two minus one gives us all those ones). If there are no duplicated bits, a&b == 0, and 1 << 1 == 1, and 1 - 1 = 0, so it means no change, the correct solution! Now, here's the problem: what if all those ones are unavailable due to the minimum value? The example I've been using is (4, 4). It would be nice to trade one of those 4's for a 3, but if the min value for each is also 4, this is impossible. The formula above would give 7, but this limitation means you can't get bigger than 4. A minimum of one is fine still - it is the same as zero due to how OR works. The problem is a minimum of two or more. This cuts off ones from the right. Oh, but not necessarily! You get a one on the end for ALL odd numbers, so unless the min == max && !(max&1), you get the one on the end. So, the bigger the gap, the smaller our mask. Since the interval is inclusive, the most significant set bits on each max can never be masked out. We'll use that as the starting point and write up a loop solution. We start at the right - the ones place - and or it in if the bit is available. It looks like the another AND filter applied to the AND that's there, but instead of using numbits(a&b), we should use numbits(something_min). Which one are we carrying those ones from? Either, really. So as long as either one works, we should be ok. Let's try it. Nope :( The max is now too small. Gah, I need to get to bed. Here's what I have: ========= uint max_c(uint max_a, uint max_b, uint min_a, uint min_b) { uint tmp = max_a | max_b; uint true_min = min(min_a, min_b); if(min_a <= 1 || min_b <= 1) tmp |= ((1 << numbits(max_a&max_b)) - 1); else { // THIS PORTION IS WRONG tmp |= ((1 << numbits(max_a&max_b)) - 1); uint mask = min(msb(max_a), msb(max_b)) - 1; for(uint v = 1; v < mask; v <<= 1) { if(true_min - v && !(true_min & v)) mask &= ~v; } tmp &= ~mask; } return tmp; } ========= -- Adam D. Ruppe http://arsdnet.net