Flipping with a Swing

By Riley Major, 2018-05-31.

When talking about bitwise math, I needed to show the inverse of a string of ones and zeros. Instead of doing it manually, I wanted to get a computer assist. Since I always have SQL Server Management Studio open, T-SQL is usually the fastest way for me to use some CPU cycles.

Swing Variable

In a typical, procedural programming language, you can’t execute a variable swap in a single statement. You need one step to set your first variable and a second step to set your second variable. But by the time the second step runs to set your second variable, the original value of the first variable is lost.

DECLARE	@a char(2) = 'WI', @b char(2) = 'MN';
SET @a = @b; /* At this point, both @a and @b store "MN". "WI" is lost. */
SET @b = @a; /* This is basically a NOOP. @b is already the same as @a. */
SELECT '@a' = @a, '@b' = @b;

Results:

@a @b
MN MN

You might think you could be tricky and perform the assignments “at the same time” by putting them on equal footing in a single SELECT statement. You might, Rabbit, you might.

DECLARE	@a char(2) = 'WI', @b char(2) = 'MN';
SELECT @a = @b, @b = @a;
SELECT '@a' = @a, '@b' = @b;

Nope. Same results:

@a @b
MN MN

To solve this, you typically introduce a third, “swing” or temporary variable.

DECLARE	@a char(2) = 'WI', @b char(2) = 'MN', @c char(2);
SET @c = @a; /* Put @a's value in a safe place. */
SET @a = @b; /* At this point, both @a and @b store "MN". But "WI" is safe in @c. */
SET @b = @c; /* Now we retrieve "WI" from @c. */
SELECT '@a' = @a, '@b' = @b;

Results:

@a @b
MN WI

Tabular Derivation

There are math tricks to avoid the extra variable, but generally they’re confusing and probably slower than just using the temporary variable.

But T-SQL affords you some syntactical tricks of its own that allow you to create swing variables– indeed, swing tables– on the fly, without separate variable declarations and assignments. A derived table can expose the original variables’ values to be used in assignment, and they can be referenced even “after” they’ve been assigned (in the course of the same SQL statement).

DECLARE	@a char(2) = 'WI', @b char(2) = 'MN';
SELECT
	@a = TempData.b,
	@b = TempData.a
FROM		(
				SELECT
					a = @a,
					b = @b
			) AS TempData;
SELECT '@a' = @a, '@b' = @b;

Back to the Bits

To flip my bits, I didn’t merely need to swap variable values. I needed to swap text values within a variable. (If I wanted to flip actual bits, I’d use the bitwise NOT operator.)

Our derived table trick won’t help here, because we don’t just need a place to store separate information temporarily. The information is all bundled together.

We could tease it apart, character by character. SQL Server 2016’s new string splitting function, unfortunately, won’t accept an empty string as a delimiter.

SELECT s.value FROM STRING_SPLIT ( '11101101010', '') AS s

Results in error:

Msg 214, Level 16, State 11, Line 19
Procedure expects parameter 'separator' of type 'nchar(1)/nvarchar(1)'.

Alternatively, we could use a tally table to break it apart based on the character position. But that’s a lot of code, and then we’d have to put the rows back together into a single string when we were done.

Any of that was going to take more time than just manually swapping characters, so I wanted something even easier. One’s first instinct might be to just replace the ones with zeros and zeroes with ones. But doing that directly, in either order, results in a ruined string of all one type:

SELECT
	ZerosFirst = 
		REPLACE
		(
			REPLACE
			(
				'111000111',
				'0',
				'1'
			),
			'1',
			'0'
		),
	OnesFirst =
		REPLACE
			(
				REPLACE
				(
					'111000111',
					'1',
					'0'
				),
				'0',
				'1'
			);

Results:

Zeros First OnesFirst
000000000 111111111

This was fundamentally the same problem as our variable swap. It don’t mean a thing if it ain’t got that swing. We need a safe place to store the original data while we make our changes.

Swing Character

When dealing with a single string, the only way to make a safe space for us to store our replaced characters is to use a character we know would otherwise never be used in the string. This is the classic problem of choosing a delimiter. For a complex scenario, using really rare, unprintable characters as CHAR(1) might be necessary. But here, a simple letter “x” will do.

First, we switch all of one character to our swing character (say, each number one to an x). Then, we switch all of the leftover zeros to ones. Then we retrieve the original ones locations from our safe space (“x”) and change those to zeros.

SELECT
	Flip = 
		REPLACE
		(
			REPLACE
			(
				REPLACE
				(
					'111000111',
					'0',
					'x'
				),
				'1',
				'0'
			),
			'x',
			'1'
		);

Result: 000111000.

And thus our bits are flipped, thanks to our swing character.

Leave a Reply

Your email address will not be published.