#bitoperators

8-bit opERatorS - ThE muSic of krAFTwERk

Found this problem today:

Given a string (for example: "a?bc?def?g"), write a program to generate all the possible strings by replacing ? with 0 and 1. Example: Input : a?b?c? Output: a0b0c0, a0b0c1, a0b1c0, a0b1c1, a1b0c0, a1b0c1, a1b1c0, a1b1c1.

Seems to be a good candidate for coding fast since it's not complicated at all. Plus, the fact that they say replace with 0 or 1 already gives you the hint that you may use some binary tricks.

How many solutions will there be? Which can be translated into how many ways to combine the 0s and the 1s. Well, depends on how many positions you have to fill.

Suppose there are 3 question marks as in the problem example. Then the last solution will have 1 replacing ? on every position. That spells 111.

I isolate all the question marks, I form a binary representation which, on its max value, gives the number of solutions for this problem. In our example case, that is 8.

You will see below how I coded the algorithm using a data structure to store the words in the text delimited by "?" . This means space complexity, but saves time when you reconstruct the solution. If you don't like storing text, use a substr call when you build a solution.

The time complexity is dependent on the number of solutions to be built. Suppose you have m questions marks in the text of length N, then the total solutions is 2^m equivalent to the number of times you have to walk the text to do the the replacements. If you glue the words with the new delimiters, you won't have to parse the text again.

To recap. the complexity is O(m*2^m) and when m is close to logN, it becomes O(n*logN).

As a note, the code works even if you have multiple questions marks on adjacent positions.

const string text = "danser?un?slow?avec?toi?"; QuestionMarkIntoBinary.Replace(text).ForEach(Console.WriteLine);

public static List Replace(string text) { var result = new List(); if (string.IsNullOrWhiteSpace(text)) { return result; } // isolate the string parts string[] parts = text.Split(new[] { '?' }); // need at least a question mark in order to build a solution // otherwise the only solution is the original text if (parts.Length < 2) { result.Add(text); return result; } // we have to generate the following series of values: // starting from 00000...0 // up to 11111...1 for (int i = 0; i < Math.Pow(2, parts.Length - 1); i++) { // get the string binary representation string bits = Convert.ToString(i, 2); // add the built solution result.Add(buildSolution(parts, bits)); } return result; } /// /// built solution using string parts /// and generated separators /// private static string buildSolution(string[] parts, string bits) { var builder = new StringBuilder(); int offset = parts.Length - 1 - bits.Length; // pad with initial 0 if needed since the binary representation // may have only a limited positions for the low value numbers for (int i = 0; i < offset; i++) { builder.Append(parts[i]); builder.Append("0"); } // alternate string with bit value for (int i = offset; i < parts.Length - 1; i++) { builder.Append(parts[i]); builder.Append(bits[i - offset]); } // don't forget the last part builder.Append(parts[parts.Length - 1]); return builder.ToString(); }

Here is an example:

Helper method for the previous entry blog

As with any other immediate bit algorithm, all it needs is scratching 0s and 1s on a piece of paper for a few minutes. Look at the example below. Say we have to turn off the bit on the marked position.

                                    |

01011110001111011011001011011011

In order to get the result, we can AND the original number with this one:

11111111111111101111111111111111

Finding the little hole? Use two parts that are ORed:

11111111111111100000000000000000 00000000000000001111111111111111

To get a series of 1, extract 1 from the immediate bigger number that looks like: 100000000. The operation can be described as: 

 (1 << i) - 1

public static int ClearBit(int n, int pos) { if (pos == 0) { return n; } int left = (1 << (VALID_LENGTH - pos)) - 1; left <<= pos; int right = (1 << (pos - 1)) - 1; return (left | right) & n; }

As a bonus, here are three other bit operations I found very useful:

1. turn off the rightmost 1 bit: n & (n - 1)

          00101010

          00101001

          -------------&

          00101000

2. isolate the rightmost 1 bit: n & (-n)

          10101100

          01010100

          -------------&

          00000100

3. turn on the righmost 0 bit: n | (n+1)

          01001111

          01010000

          -------------|

Given an int, find the closest greater number with the same number of 1 bits. Assume the number is positive.

Maybe an example would help. Let's say I have a number that looks like this in its binary representation:

01001010001100100011000101001011 Taking a closer look at the last four bits:

1011

Then the next bigger number having three 1 bits, would be:

1101

A jump from 11 to 13 it's not that much. The idea is to find that combination of 01 at close to the end of the number as possible and switch the two bits. 

Here's my code:

private const int VALID_LENGTH = 32; // we need to find the last 0 followed by a 1 // we'll put 1 where we found the 0 // and we'll put 0 on the first 1 at its right public static int GetNextBiggerNumberWithTheSameNumberOfOnes(int n) { if (n <= 0) { return -1; } int result = 0; int curPos = 1; bool replaced = false; // the position of 1 to be replaced int posOne = 0; // start iterating the bits from the right while (n > 0) { if ((n & 1) == 1) { // we found a bit of 1 if (!replaced) { posOne = curPos; } result |= 1 << (curPos - 1); } else { if (!replaced) { if (posOne > 0) { // found a 0 after a 1, replace the 0 result |= 1 << (curPos - 1); replaced = true; } } } n >>= 1; curPos++; } if (!replaced && curPos < VALID_LENGTH - 1) // don't hurt the sign bit { // number looks like 1111...10000...0 // all is not lost, we'll try putting one in front result = (1 << (curPos - 1)) + result; replaced = true; } if (!replaced) { // we tried our best return -1; } // one more thing left, put 0 in the left most position where we found a 1 return clearBit(result, posOne); }

Examples:

01110110011100001111000100011101 01110110011100001111000100011110

00000101000011110111110001001111 00000101000011110111110001010111

I iterate from the right most position looking for my pattern, once I find it, I put 1 in place of 0, mind the older position of 1 as posOne and keep going. When I reach the end, if there was a replace in place, I just clear the bit on my saved position.

There's a special case I address in the code where the number tails on 0 without encountering any 1.

Which means no +.

This problem is completely useless of course, but it contains a nice hint in the solution. When you XOR the bits corresponding to a bit position in the two numbers, you will get the bit in the result. In order to compute the carry, check that you have the two bits 1 for the bit position or that at least one of them is 1 and you have a carry of 1.

See below the code.