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 = 0x43512, d = 3 -> Result : 0x42513
                               - 0x10101 <- the zero's are there because the digits
                              ----------    over them are smaller than 3
                                 0x32411

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?

CodePudding user response：

It's possible. And fairly straightforward for constant n.

For the example with n=3 and input x

Note that a nibble is >= 3 if

• The 8s bit is set or
• The 4s bit is set or
• The 2s bit and 1s bit are both set

Therefore

subtrahend = ((x >> 3) | (x >> 2) | ((x >> 1) & x)) & 0x11111111;
result = x - subtrahend;

Doing that for variable n in branchless code will not be fun. If branches are acceptable you could simply pre-analyze all the minimized logic functions and use switch (n) to pick from them.

CodePudding user response：

I don't think there's any support for this specific operation in the standard library, but you could create your own function for it.

• Create an index_sequence with the number of nibbles in the type as template parameters.
• Extract each nibble by right shifting and do a binary AND 0xF.
• Check if the result is >= the limit you've supplied
• Left shift the boolean result the same amount of bits.
• Combine the results with a fold over |.

#include <climits>
#include <type_traits>
#include <utility>

template <class T>
T sub(T val, std::type_identity_t<T> lim) {
    return val - [=]<std::size_t... I>(std::index_sequence<I...>) {
        return ((T((val >> (I * 4) & 0xF) >= lim) << (I * 4)) | ...);
    }(std::make_index_sequence<sizeof(T) * CHAR_BIT / 4>{});
}

Demo

CodePudding user response：

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

Using a SWAR average,

uint64_t L = 0x1111111111111111;
uint64_t v = L * n;
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 n.

As long as n >= 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 n can be zero then that would require more care.