2
votes

I have the bit equation:

x + y = x | y

How to solve this equation? I need to find k-th smallest positive integer y for which equation holds. Maybe there is any algorithm? Where can i read about it? Ofcause i simply tried to solve it like this (in Pascal):

uses crt;
var x,y,k,count:integer;

begin readln(x,k); count:=0;

for y:=1 to 10000 do
    if((x+y) = (x or y)) then 
    begin
        inc(count);
        if(count = k) then
        begin
            WriteLn('y= ',y); 
            break;
        end;
    end;

But the code is very slow!

Thanks in advance!

4
This equation has many, many solutions. When you ask how to solve it, do you mean you want all of them? - Wintermute
The first and most obvious solution is x = 0, y = 0. Or do you want all the solutions ? - Paul R
Ok, i need to find k-th smallest positive integer y for which equation holds - user2660964
AFAICS x + y is equal to x | y when ~(~x | ~y) is zero - Columbo
@Columbo: Or, more simply, when x & y is 0. One way to prove that would be to prove that x+y === (x|y)+(x&y) - rici

4 Answers

3
votes

This equation can be solved by making a simple observation about + and | on a single bit value:

  • When both values are 0, both operations produce 0,
  • When the values are 1 and 0 or 0 and 1, both operations produce 1,
  • When both values are 1, the results are different; also, + produces a "carry", which changes the adjacent bit.

Since you are looking for equality of x + y and x | y combinations, all you need to check is that there are no bits that are set to 1 in both numbers. In other words, any pair x, y such that x & y == 0 will make your equation true, while any pair such that x & y != 0 will turn your equation false.

In order to find k smallest y for which the equation holds for a given x, you can try all values of y, decrementing k each time you find x & y == 0. Once k reaches zero, print the current value of y.

2
votes

The total number of solutions is 3/4 of the total number of possible combinations of x and y values. This is because your equation will be satisfied whenever there are no carries within x + y. So for each bit, the three combinations of corresponding x and y bits 00, 01 and 10 generate no carry, and only 11 generates a carry.

0
votes

I'm aware that there is an accepted solution, but there is a much faster way to find the kth-smallest integer for which this solution holds than brute-forcing a solution the way it recommends.

Since you mentioned that your original code (which uses this approach) is much too slow, I figured you'd like a solution that has O(bits in the integer type) runtime complexity. With it, I can generate the first 500000 solutions (all of them, not just the 500000th) for x = 1234567890 in about 1/10th of a second on my i7 (redirecting the output to /dev/null, otherwise that becomes the bottleneck), although that is of course less time than would make for a useful benchmark, and am be able to generate each individual one with roughly the same speed, whereas counting y up to the 500000th solution in the brute-force approach would mean, in this example, checking over 500 million numbers.

The key insight to have is that the only numbers that solve the equation x + y = x | y for a given x are those that have a subset of the bits in ~x set. Thus this becomes a question of finding the kth-smallest such subset, and that can be done with a binary search -- this nets us the O(bits) complexity.

In other words, knowing which bits can be used in a solution enables us to construct the kth solution from the most significant bit downwards because setting the nth-lowest bit (of those that can be used) in the ith solution (in which it is not yet set) generates the (i + 2n-1)th solution. This means we can walk through the usable bits, decide for each whether setting it in the solution we currently have would generate a solution with an ordinal number greater than k, and set it or not depending on that.

The code is C++, because the question is tagged C++ and I like it better than Pascal.

#include <bitset>
#include <iostream>
#include <stdexcept>

// An artifact of the development process. I used it to test that
// the exception is thrown properly if there are less than k solutions.
enum { BITS_USED = 31 };

// Counts the bits set in an integer
unsigned bitcount(unsigned x)  {
  unsigned count = 0;

  while(x != 0) {
    ++count;
    x &= x - 1;
  }

  return count;
}

// Finds the highest bit set in x, starting to look at start
// (which will be the previously highest bit the way we use it)
unsigned highest_set_bit(unsigned x, unsigned start = 1 << (BITS_USED - 1)) {
  unsigned mask = start;

  while(mask != 0 && (x & mask) == 0) {
    mask >>= 1;
  }

  return mask;
}

// This function does the binary search.
unsigned find_kth_complement(unsigned x, unsigned k) {
  // (rest_mask) is the complement of (x), or at least the bits we take into
  // consideration (see comment on BITS_USED above).
  unsigned rest_mask = ~x & ((1u << BITS_USED) - 1);
  unsigned rest_bits = bitcount(rest_mask);
  unsigned bit       = highest_set_bit(rest_mask);

  // (curmask) will be updated to contain the bits we already know the
  // (k)th solution will have set. It will be built from the most significant
  // bit downwards and always be a solution itself (!). Setting new, ever
  // less significant bits in it will make it larger until it is the (k)th
  // solution.
  unsigned curmask   = 0;

  while(rest_mask != 0) {
    rest_mask &= ~bit;
    --rest_bits;

    // Here now the binary search: We know that (rest_bits) bits are
    // set in (rest_mask), which is (~x) without the bits we already
    // know the solution will have set. We know therefore that there
    // are (skip) = 2^(rest_bits) solutions that have the bit in (bit)
    // set, and equally many that have it unset.
    unsigned skip = 1u << rest_bits;

    // So: Setting the highest bit of the rest mask in (curmask) will
    // propel (curmask) (skip) solutions ahead. We can only do this if
    // we still have to skip more than that many solutions. (k) will
    // be adjusted to be the number of solutions left to skip.
    if(k >= skip) {
      curmask |= bit;
      k -= skip;
    }

    bit = highest_set_bit(rest_mask, bit);
  }

  // if (k) is not zero here, there were not enough solutions to skip.
  if(k != 0) {
    throw std::logic_error("There are less than k solutions for the given x");
  }

  return curmask;
}

int main() {
  unsigned x = 1234567890;
  unsigned y = ~x & 0xff;

  std::cout << std::bitset<BITS_USED>(x) << std::endl;

  // Taking it for a ride here: Generate the first 500k solutions.
  // Printing them is done in binary because it is easier to see that it
  // works that way.
  for(unsigned i = 0; i < 500000; ++i) {
    std::cout << std::bitset<BITS_USED>(find_kth_complement(x, i)) << "\n";
  }
}
-1
votes

Simplest answer to this is negation:

unsigned y = ~x;

Because (x & ~x) == 0.

To get k-th you should map bits of k to 1-bits of y. This will do only 32 (or 64 if you use x64) steps to complete.

unsigned find(unsigned y, unsigned k)
{
    int i = 0, j = 0;
    unsigned result = 0;
    for (i = 0; i < sizeof(unsigned)*8; ++i)
    {
        if (y & (1 << i))
        {
            if (k & (1 << j))
                result |= y & (1 << i);
            ++j;
            if (k < (1 << j))
                break; //we used all bits of k
        }
        if (y < (1 << i))
            break; //we used all 1-bits of y
    }
    return result;
}

Visualization:

y:     110010011
k:         11001
       11  0  01 //we skip some position
r:     110000001

To get list of fist k numbers you can do loop:

for (unsigned i = 1; i <= k; ++i)
    std::cout << find(~x, i) << std::endl;