Subtract 1 from all digits of a hex which are smaller than given value d in C++

Question

I have the following problem : I have a hex number (datatype : std::uint64_t) in C++, and the hex number contains all the digits from 1 to a given n. We also have given another digit d <= n. Is it possible to subtract 1 from all the digits of the hex number, which are greater or equal than n? Here's an example of what I'm expecting :

hex = 0x42513, d = 3 -> Result : 0x42513
                               - 0x10101 <- the zero's are there because the digits
                              ----------    over them are smaller than 3
                                 0x32412

I have already tried out using a for-loop with left and right-shifts to achieve the result, but now I'm interested if there exists a solution without using a loop but instead using bit manipulation only?

Answer 1

There are some ways, even when d is not known in advance.

Using a SWAR average,

uint64_t L = 0x1111111111111111;
uint64_t v = L * d;
uint64_t decrementedHighNibbles = x - L + ((SWAR_AVG(~x, v, L) >> 3) & L);

Where:

uint64_t SWAR_AVG(uint64_t x, uint64_t y, uint64_t L) {
    return (x & y) + (((x ^ y) & ~L) >> 1);
}

For the rest of the explanation, let's consider just one nibble, standard SWAR techniques take care of applying the same operation to every nibble.

The basis for the trick is that the top bit of avg(~x, v) will be set if and only if x < v. That's the opposite condition of what we wanted, so instead of subtracting the top bit of the nibble from that nibble, 1 is subtracted unconditionally first, and then 1 is conditionally added back if the nibble was less than d.

As long as d >= 1, subtracting and adding 1 to the nibbles does not require the special SWAR-addition/subtraction, since there will automatically not be a borrow into the next nibble (which could only happen when subtracting 1 from a nibble that is zero). During the unconditional subtraction of 1 from every nibble, some borrows may cross between nibbles, but that would then be undone by the subsequent addition. If d can be zero then that would require more care.

Here is an alternative method using a "rounded up" SWAR average. Where (x & y) + ((x ^ y) >> 1) computes the average of x and y rounded down, (x | y) - ((x ^ y) >> 1) computes the average of x and y rounded up. The SWAR version of that is:

uint64_t SWAR_AVG_UP(uint64_t x, uint64_t y, uint64_t L) {
    return (x | y) - (((x ^ y) & ~L) >> 1);
}

While avg(~x, y) computes x < y in the top bit, avg_up(~x, y) computes x <= y in the top bit. We need x >= v so, so use SWAR_AVG_UP(x, ~v, L):

uint64_t decrementedHighNibbles = x - ((SWAR_AVG_UP(x, ~v, L) >> 3) & L);