18
\$\begingroup\$

Exposition

In this challenge, I am talking about ARM assembly language. ARM is a 32-bit RISC processor; I'll use instruction set up to architecture v6.

To load a constant ("immediate") value into a register, use the MOV instruction:

MOV r8, #42

To load negative values, use the MVN instruction, with a bit-complement of the operand:

MVN r8, #41

You can't load any 32-bit value with this instruction. Acceptable values are:

  • Any 8-bit value: 0...255
  • Any 8-bit value, rotated right by an even number of bits, 2...30
  • A bit-complement of any value as described above (a good assembler will accept such operands and turn MOV into MVN)

Challenge

Make code which determines if the given input is a valid operand for a MOV instruction.

Input

A number in the range 0...232-1 or -231...231-1, whatever is easier.

If you represent the number as a string, use decimal notation.

Output

True or false, as usual.

Examples

(some of them taken from this nice site with explanations).

True:

0x000000FF
0xffffd63f
0xFF000000
0b1010101100000000 (8 arbitrary bits, followed by even number of zeros)
0b11110000000000000000000000001111 (11111111 rotated right by 4 bits)

False:

0x000001FE
0xF000F000
0x55550000
0xfffffe01
0b10101011000000000 (8 bits but followed by odd number of zeros)
0b11110000000000000010000000001111 (too many spread-out 1-bits)
\$\endgroup\$
6
  • 2
    \$\begingroup\$ Do you have any examples and why they are or are not valid? \$\endgroup\$
    – Tbw
    Feb 7 at 18:38
  • \$\begingroup\$ Added some examples. Thanks for reminding! \$\endgroup\$
    – anatolyg
    Feb 7 at 18:49
  • \$\begingroup\$ Is the input in hex, binary, decimal, or is it up to us? \$\endgroup\$
    – Xcali
    Feb 7 at 18:56
  • 3
    \$\begingroup\$ I'm waiting on an answer written in ARM \$\endgroup\$
    – qwr
    Feb 7 at 21:32
  • 1
    \$\begingroup\$ @qwr: Or in bash using as and checking for error messages :P A version of ARM asm for this can be found on ARMv5 and earlier MOV and MVN operands using ARMv4 (arm7tdmi), just brute-force trying every rotation. Golf wasn't the goal but the author describes it as "brutally compact". GNU Binutils as also just brute-forces the check, see the other answer on that SO Q&A. \$\endgroup\$ Feb 8 at 5:52

12 Answers 12

12
\$\begingroup\$

Rust, 52 49 bytes

|n|(0..16).any(|i|(n<<33^n<<32^n*2^n)<<i*2>>41<1)

Attempt This Online!

A closure that takes an unsigned 32-bit value of type u64 and returns a bool. -3 thanks to corvus_192.

  • A 32-bit value n is acceptable
  • \$\Leftrightarrow\$ n has a run of 24 equal bits at an even offset, when viewed cyclically
  • \$\Leftrightarrow\$ n | n << 32 has a run of 24 equal bits at an even offset, between 0 and 30 inclusive
  • \$\Leftrightarrow\$ (n | n << 32) ^ ((n | n << 32) << 1) has a run of 23 zero bits at an even offset between 0 and 30 inclusive, counting from the high end
  • \$\Leftrightarrow\$ n<<33^n<<32^n<<1^n has a run of 23 zero bits at an even offset between 0 and 30 inclusive, counting from the high end
  • \$\Leftrightarrow\$ (n<<33^n<<32^n<<1^n)<<i>>41 is zero for some even i between 0 and 30 inclusive
\$\endgroup\$
1
  • \$\begingroup\$ -3 bytes: If you give a type signature to f, you can get rid of the u64 suffix on the 1 at the end \$\endgroup\$
    – corvus_192
    Feb 8 at 20:46
6
\$\begingroup\$

Charcoal, 21 bytes

Nθ⊙ 3№×²◧⍘θ 123¹⁶×¹²ι

Attempt This Online! Will accept input in decimal by default, but also hex with 0x prefix and binary with 0b prefix. Outputs a Charcoal boolean, i.e. - for valid, nothing if not. Explanation:

Nθ                      First input as a number
    3                   Literal string ` 3`
  ⊙                     Any character satisfies
          θ             Input number
         ⍘              Converted to custom base
            123         Literal string ` 123`
        ◧               (Left) Padded to length
               ¹⁶      Literal integer `16` 
      ×                 Repeated by
       ²                Literal integer `2`
     №                  Contains
                    ι   Current character
                 ×      Repeated by
                  ¹²    Literal integer `12`
\$\endgroup\$
4
\$\begingroup\$

Python, 52 bytes

f=lambda n:n>4**32or 0<n%~-4**16>>8<8**8-1and f(n*4)

Attempt This Online!

Returns False for True and True for False.

How?

Uses mod 0xffffffff to get from a linear left shift to a cyclic left shift. Advantages of linear being 1) Python actually has it. 2) easier stopping criterion.

\$\endgroup\$
4
\$\begingroup\$

Go, 157 147 bytes

import."math/bits"
func f(n uint32)(r bool){F:=uint32(0xFF)
for k:=2;k<31;k+=2{j:=RotateLeft32(n,k)
if r=j<=F||^j<=F;r{return}}
return n<=F||^n<=F}

Attempt This Online!

Input is an unsigned 32-bit integer.

  • -10 bytes: use a comparison rather than an equality and bitwise-and.

Explanation

import."math/bits"
func f(n uint32)(r bool){
F:=uint32(0xFF)
for k:=2;k<31;k+=2{          // rotation check
j:=RotateLeft32(n,k)         // rotate left an even number of times
if r=j<=F||^j<=&F;r{return}} // if 8-bit or its complement is 8-bit, return true
return n<=F||^n<=F}          // return if 8-bit or its complement is 8-bit

Go, 121 bytes

func f(n,k uint32)int{F:=uint32(0xFF)
if n&^F>0{k--
if k<1{return 0}
j:=n*4|n>>30
if k&1>0{j=^n}
return f(j,k)}
return 1}

Attempt This Online!

A direct port of @Arnauld's JS answer.

\$\endgroup\$
2
  • \$\begingroup\$ Can you replace j==j&F with j<=F to check for the unsigned value having no high bits? That's the same thing as being unsigned below or equal to 0xFF, value-range 0..0xFF. And I think ^j<=F to check for the inverse fitting. So we want to accept a value-range from -256 .. 255, like j+256<=511 I think, since this version of the question doesn't ask us to figure out which of mvn or mov can encode it. \$\endgroup\$ Feb 8 at 6:15
  • \$\begingroup\$ IDK if that helps in Go, if you'd need uint32() around each constant, but a range check via subtract (of a negative in this case) and an unsigned compare is a standard trick in assembly (which compilers do for us in higher-level languages): double condition checking in assembly \$\endgroup\$ Feb 8 at 6:24
4
\$\begingroup\$

ARMv2, 32 28 bytes

Input is in R0, output is in R1 which is zero if the input is an invalid constant. CMN trick stolen from Notlikethat's answer to the Stack Overflow question linked by @PeterCordes.

VALID:  MOV R1, #-16
LOOP:   MOV R0, R0, ROR#2
        CMP R0, #256
        CMNCC R0, #256        @ compare with -256, predicated on Carry Clear
        ADDSCC R1, R1, #1     @ Add and Set flags if Carry Clear
        BCC LOOP
        MOVS R15, R14         @ return

This is ARM mode so each instruction is 4 bytes, unlike Thumb or Thumb 2.
movs r15, r14 copies the return address to the program counter, mov pc, lr, returning from the function like bx lr in modern ARM code.

Alternative version using @Bubbler's trick of XORing the input with itself rotated left one bit, which still works with CMP (but not my original 32-byte TST version, which is why I didn't use that approach at the time). Input is in R0, output is in ZF which is set or R0 which is zero if the input is an invalid constant.

VALID:  EOR R1, R0, R0, ROR#31
        MOV R0, #-16
LOOP:   MOV R1, R1, ROR#2
        CMP R1, #512
        ADDSCC R0, R0, #1     @ Add and Set flags if Carry Clear
        BCC LOOP
        MOV R15, R14          @ return
\$\endgroup\$
4
  • \$\begingroup\$ This can be 26 bytes for Thumb2 mode, with an itt cc block covering the predicated instructions, and a 2-byte bx lr instead of movs pc, lr to return. The savings are in the bcc and bx lr, partially cancelled out by the 2-byte itt. Unfortunately movs r1, #-16 is a 4-byte instruction, and so is addscc inside an IT block (unlike addcc), but it's necessary to for it to set flags if R1 changes from -1 to 0 so we exit the loop after trying all possibilities. (And rotate-immediate isn't available as a 16-bit thumb instruction, only a 32-bit form.) \$\endgroup\$ Feb 9 at 6:32
  • \$\begingroup\$ I think any other flag-setting ALU instruction in the ITT is still 4 bytes in Thumb 2, so the way to save space would be to replace movs r1, #-16 with a 16-bit instruction. Perhaps movs r1, #128 and use lslsCC r1, #1 which eventually sets carry when shifting out that last set bit. (Redundantly checking some rotations a second time. Or can we start with r1=1 and lsls r1, #2? I think so.) godbolt.org/z/sMPbsrh89 shows both 24-byte Thumb2 versions. addsCC r1, #-1 and subsCC r1, #1 don't work, setting Carry opposite of what we want while r1 hasn't crossed non-zero yet. \$\endgroup\$ Feb 9 at 6:53
  • \$\begingroup\$ @PeterCordes I only ever learned ARMv2 on the original Acorn PCs so I'll take your word for it on Thumb2. \$\endgroup\$
    – Neil
    Feb 9 at 8:01
  • \$\begingroup\$ Sorry accidentally downvoted this \$\endgroup\$
    – noodle man
    Feb 12 at 13:57
2
\$\begingroup\$

Retina, 101 bytes

.+
$.(23283064365386962890625**
16{`.+$
$.(4**
)r`(.?)(.{1,32})$
$.($1*)¶$2
A`$
¶

$
$`
0`0{12}|3{12}

Try it online! Link includes test cases. Outputs 1 for valid, 0 for invalid. Explanation:

.+
$.(23283064365386962890625**
16{`.+$
$.(4**
)r`(.?)(.{1,32})$
$.($1*)¶$2
A`$

Convert the input to 16 base 4 digits. (This method is required for very large integers or even for large integers where the traditional method would cause the process to run out of memory.)

¶

$
$`

Join the digits together and then duplicate the string.

0`0{12}|3{12}

Check for 12 repeated 0s or 3s. (If any non-zero output is acceptable, the 0` can be removed to save two bytes.)

\$\endgroup\$
2
\$\begingroup\$

JavaScript (Node.js), 43 bytes

f=n=>++i&31&&n>>8==n>>31|f(n>>>2|n<<30);i=0

Try it online!

Note: This function will not be reusable after about 248 invokes. I would argue that should be fine according to the spirit of code-golf though. And fix the limit may cost 2 more bytes.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ @Arnauld should be fixed, by reducing 2^49 to 2^48 \$\endgroup\$
    – tsh
    Feb 8 at 0:58
  • 1
    \$\begingroup\$ 42 bytes? \$\endgroup\$
    – Arnauld
    Feb 8 at 13:48
2
\$\begingroup\$

05AB1E, 17 bytes

4B16°+¦2×30S12×åà

Port of @Neil's Charcoal answer, so make sure to upvote that answer as well.

Input as an integer.

Try it online or verify all test cases.

Explanation:

4B                # Convert the (implicit) input-integer to base-4
  16°             # Push 10**16
     +            # Add it to the base-4 number (as base-10 addition)
      ¦           # Remove the leading 1
       2×         # Repeat this string two times
         30S      # Push [3,0]
            12×   # Repeat both 12 times
               å  # Check if the earlier string contains a substring of 12 3s or 0s
                à # Check if either of the two is truthy
                  # (after which the result is output implicitly)
\$\endgroup\$
2
\$\begingroup\$

Ada/GNAT, 152 bytes

type T is mod 2**32;function G(X:T;C:T:=0) return Boolean is (C<30 and then ((((X and 255)=X or (X or not 255)=X) or else G((X mod 4)*2**30+X/4,C+1))));

G is a recursive function that:

  1. Takes a type T, which is a mod. Mod types are like Integers, except they wrap around when they overflow and you can do bitwise operations on them.

  2. Defaults C to 0 and uses it to check for too many recursions. This was way fewer bytes than writing a loop structure, not just because of the verbose loop syntax in Ada but also because the inline subprogram syntax couldn't be usable with a loop. I picked 30 because it was no more bytes than more sensible values like 15 or 16 that I'd have to do more testing on.

  3. Does bitwise logic between the input X and 255/not 255. I honestly didn't expect "not 255" to work, but as it turns out, this does a logical inverse as if it were a variable. These two comparisons basically enforce the rule that all the meaningful data must be within a range of eight contiguous bits. 255 being 00000000000000000000000011111111, and not 255 being 11111111111111111111111100000000.

  4. Does the arithmetic equivalent of rotating by 2 and uses this with an incremented C to call its next iteration. There is a builtin for rotations, but using it required a with and a function call, so doing this turned out to be less verbose.

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 47 bytes

Returns 0 or 1.

f=(n,m=~255)=>n&m&&~n&m?m%96&&f(n,m*4|m>>>30):1

Try it online!

Commented

f = (          // f is a recursive function taking:
  n,           //   n = input
  m = ~255     //   m = mask, initialized to ~255 (note that this gives
               //   the signed value -256 rather than 0xFFFFFF00, which
               //   is important for the modulo 96 test)
) =>           //
n & m &&       // if n & m is not 0
~n & m ?       // and ~n & m is not 0:
  m % 96 &&    //   if m is not equal to 0x3FFFFFC0 (the last rotation
               //   which is the only one to be a multiple of 96):
    f(         //     do a recursive call:
      n,       //       pass n unchanged
      m * 4 |  //       rotate m by 2 positions to the left
      m >>> 30 //       (the result is still signed)
    )          //     end of recursive call
:              // else:
  1            //   success: return 1
\$\endgroup\$
1
\$\begingroup\$

Jelly, 17 bytes

+Ø%BḊṙ⁴ḶḤ¤;¬$ḄṂ<⁹

Try it online!

A monadic link taking an integer and returning 1 for valid and two for invalid.

Explanation

+Ø%               | Add 2**32
   B              | Convert to binary
    Ḋ             | Remove first digit
     ṙ⁴ḶḤ¤        | Rotate left by each of (0 to 15 doubled)
          ;¬$     | Concatenate to binary not of this
             Ḅ    | Unbinary
              Ṃ   | Max
               <⁹ | < 256
\$\endgroup\$
1
\$\begingroup\$

ARMv6M (Cortex-M0), 38 bytes

;@ Pre-UAL syntax
;@ bool isValidARMImm(int _X);
_isValidARMImm:
            TST R0,R0           ;@ test negative
            BPL 1f
                NEG R0,R0       ;@ convert to positive
1:
            TST R0,R0           ;@ test zero
            BEQ 3f              ;@ branch to true if zero
            MOV R1,R0           ;@ copy to work register
            MOV R2,#0x00        ;@ set shifted bit count to 0
2:
                LSR R1,#1       ;@ remove following 0 bits
                BCS 1f          ;@ end if 1 bit shifted in carry flag
                ADD R2,#0x01    ;@ count following 0 bits
                B 2b            ;@ loop
1:
            LSR R0,R2           ;@ shift out 0 bits
            UXTB R1,R0          ;@ unsigned byte extend
            CMP R0,R1           ;@ test (int)R0 == (byte)R1
            BEQ 3f              ;@ branch to true case if equal
                MOV R0,#0x00    ;@ false
                BX LR
3:
            MOV R0,#0x01        ;@ true
            BX LR

8 bytes can be saved by returning the result in the zero flag instead of R0.

_isValidARMImm_ZeroFlag:
            TST R0,R0           ;@ test negative
            BPL 1f
                MVN R0,R0       ;@ convert to positive
1:
            TST R0,R0           ;@ test zero
            BEQ 3f              ;@ branch to true if zero
            MOV R1,R0           ;@ copy to work register
            MOV R2,#0x00        ;@ set shifted bit count to 0
2:
                LSR R1,#1       ;@ remove following 0 bits
                BCS 3f          ;@ end if 1 bit shifted in carry flag
                ADD R2,#0x01    ;@ count following 0 bits
                B 2b            ;@ loop
3:
            LSR R0,R2           ;@ shift out 0 bits
            UXTB R1,R0          ;@ unsigned byte extend
            CMP R0,R1           ;@ test (int)R0 == (byte)R1
            BX LR
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.