Constructing a hex number by shifting, inverting and adding +/- 1

Question

I'm trying to save a number 0xFD00 in a register (MIC-1 architecture). There are registers:

• 0
• +1
• -1
• AMASK: 0x0FFF
• SMASK: 0x00FF

I can do left, right bit shifts and inverses. It is also possible to add values like SMASK + SMASK or AMASK + (-1). I can get 0xF000 with inverse(AMASK), but I'm not sure how to get 0xFD00 without too many steps.

Answer 1

The most efficient sequence so far is @Falk Hüffner's answer, 3 operations. (Although it involves a + that isn't adding +1 or -1, or a value to itself).
This answer shows a way that takes 4 operations of the kinds explicitly mentioned in the question title.

---

0xFD is 0b11111101. So it has a bunch of contiguous bits, and one other stray set bit. One simple way would be

• start with all-ones (-1, ~0, or 0 - 1)
• left shift by 2 to get ...11111100
• add 1 to get ...11111101 (0x...FD)
• shift to the top of the register, shifting in low 0s and shifting out the high 1s, leaving the 0xFD at the top, with 8 low zeros.

I don't know MIC-1, but from your description it sounds like it can do those steps. If it can only shift by 1 position at a time, it will take 2 + 8 total shift instructions. There might be other ways to construct this constant more efficiently, maybe with something I'm not thinking of, or maybe with some capability the machine has.

---

Taking advantage of AMASK / SMASK and the way add / sub carry-propagation can flip a sequence of 1 / 0 bits respectively, along with Aki's observation that ~0xfd00 = 0x02ff, we can do the following:

initial AMASK = 0x00FF

AMASK += 1     (0x0100)
AMASK += AMASK (0x0200)  (left shift)
AMASK += SMASM (0x02FF)
NOT AMASK      (0xFD00)

See https://catonmat.net/low-level-bit-hacks for a nice intro to the kinds of shenanigans you can get up to with bitwise operations. (Although many of those also require AND, OR, or XOR. E.g. clearing the lowest set bit via x &= (x-1))

---

(Related: What are the best instruction sequences to generate vector constants on the fly? for x86 SIMD vectors: similar problem, you can generate -1 on the fly cheaply without loading from memory, and feed it through various other instructions like left shift, (SSSE3) absolute value. But only worth doing for short sequences, otherwise just load from memory or mov-immediate to integer registers and movd xmm0, eax)

---

Hex is just a way to represent numbers in text, e.g. ASCII. You could call it a serialization format.

0xFD00 is just another way to write 64768 (base 10) or 0b1111110100000000 (base 2). So you're just constructing a number in a register out of shifts and inc/dec. Assuming your bit-shifts multiply / divide by 2, not 10 or 16, those are binary operations so this is a binary number. It's just convenient to express the desired binary number in a compact format like hex, but at no point do you actually need hex, like a string of base-16 ASCII digits.

It's not a "hex number" when you construct it in a register, it's just a number. If anything it's binary.

Answer 2

Assuming addition is possible with two registers and not just a constant, and left shift just drops the bits shifted out of the 16-bit word:

t = ~SMASK    // 0xff00
return t + (t << 1)

An alternative, if shifting is possible by arbitrary constants and not just 1, is

t = SMASK
t += -1
t += -1
t <<= 8

Answer 3

The inverse of 0xFD00 == 0b00000010 11111111 = 0x02ff

This can be achieved with the SMASK = 0x00FF * 3 + 2, or simply with SMASK | (1 << 9), if that's available.

a = smask
b = smask << 1
a = a + b
a++
a++
return ~a