[math-fun] bit-shift with skips

20 Apr 2014

      Recall the (IMHO very neat) method to generate the subsets
of a given bitset (look at the methods next() and prev() ):

class bit_subset
// Generate all all subsets of bits of  a given word.
//
// E.g. for the word ('.' printed for unset bits)
//   ...11.1.
// these words are produced by subsequent next()-calls:
//   ......1.
//   ....1...
//   ....1.1.
//   ...1....
//   ...1..1.
//   ...11...
//   ...11.1.
//   ........
//
{
protected:
    ulong U;  // current subset
    ulong V;  // the full set

public:
    explicit bit_subset(ulong v) : U(0), V(v)  { ; }
    ~bit_subset()  { ; }

    ulong current()  const  { return U; }
    ulong full_set()  const  { return V; }

    ulong next()  { U = (U - V) & V;  return U; }
    ulong prev()  { U = (U - 1) & V;  return U; }

    ulong first(ulong v)  { V=v;  U=0;  return U; }
    ulong first()  { first(V);  return U; }

    ulong last(ulong v)  { V=v;  U=v;  return U; }
    ulong last()  { last(V);  return U; }

    ulong shift_left()  { /* ?? what ?? */ }
};

I ask you to fill in the shift_left() method.
It shall do a left shift by one position as
shown in the following examples:

V ..........111111  <--= the full set

U ..........111.11  <--= the subset we start with
  ..........11.11.
  ..........1.11..
  ...........11...
  ..........11....
  ..........1.....
  ................

(We always start with U the full set except for the third lowest bit.)

V ....111111..1.1.

U ....11111...1.1.
  ....1111.1..1...
  ....111.11......
  ....11.11.......
  ....1.11........
  .....11.........
  ....11..........
  ....1...........
  ................

V ..1.1.111..11..1

U ..1.1.111...1..1
  ..1.1.11...11...
  ..1.1.1.1..1....
  ..1.1..11.......
  ..1...11........
  ....1.1.........
  ..1.1...........
  ..1.............
  ................

V ..1.1.111...1.11

U ..1.1.111.....11
  ..1.1.11....1.1.
  ..1.1.1.1...1...
  ..1.1..11.......
  ..1...11........
  ....1.1.........
  ..1.1...........
  ..1.............
  ................

V ..1.1.111.....11

U ..1.1.11......11
  ..1.1.1.1.....1.
  ..1.1..11.......
  ..1...11........
  ....1.1.........
  ..1.1...........
  ..1.............
  ................

V ...1........1.1.

U ............1.1.
  ...1........1...
  ...1............
  ................

Your code shall be O(1).

And awesome.

Hint: start rewriting next() as
    ulong next()  { U = (U + 1 + ~V) & V;  return U; }
This highlights that the gaps between the bits of U are
filled with ones to let the addition(s) propagate.

Spoiler below.

Spoiler belowerer.

Spoiler more belowerer.

Shpoiler shtill belowerer, skrollen Sie schnell!

---------- SPOILER ---------- :

    ulong shift_left()  { U = ( (U << 1) + ~V ) & V;  return U; }

Came up with that yesterday night only.
Has anyone seen anything alike?

The situation for
    ulong shift_right()  { /* Try! Har, har, har! */ }
is quite different, because we do not have the equivalent
for bits propagating to the right.  A revbin would (at least
partially) mitigate the situation.

Challenge: write a shift_right() (O(log(n)) is just fine!)
that doesn't totally suck.  I gave up on that.

Best,  jj

[math-fun] bit-shift with skips

Joerg Arndt