0

I want to set the first N bits of a register to 1. For example, if N is 3 then the register would be: ...00000111. Is there an instruction or short-form way to do this? The way I'm currently doing it is:

   mov $0, %eax
   test %esi, %esi
   jz end
 loop:
   add $0b1, %eax
   dec %esi
   jz end_loop
   shl %eax
   jmp loop
  exit:
    ...
samuelbrody1249
  • 4,379
  • 1
  • 15
  • 58
  • 1
    Powers of 2 have the pattern `00100000`. Subtract one from that and you get `00011111`, for example. – Erik Eidt Sep 25 '20 at 04:13
  • @ErikEidt so that would be three instructions then like Nate shows below? Or can you do it in less than a `load 1` `shift left` `subtract 1` ? – samuelbrody1249 Sep 25 '20 at 04:16
  • Do you want to *shift in* 3 `1` bits into an existing register? If not, the normal way to set bits is with OR, because it doesn't care about their previous value. – Peter Cordes Sep 25 '20 at 04:19
  • 1
    If the amount is a constant, you can precompute the value, i.e. use your slide rule to compute it and type that number into the program so it doesn't have to do the math at runtime. – Erik Eidt Sep 25 '20 at 04:24
  • @PeterCordes could you please clarify what you mean about "shift in 3" bits? Do you mean like doing `xor %eax, %eax` `or %eax 0b111` ? – samuelbrody1249 Sep 25 '20 at 04:44
  • 1
    I mean if you have an existing register containing `ABCDEFGH`, you could get a result like `DEFGH111`. Like you were doing 1 bit at a time starting with zero. But yes, of course the better way is just `shl $3, %eax` / `or $(1<<3) - 1, %eax` if you had some existing register and wanted to shift in ones instead of zeros. (BTW, your last edit make your loop a lot clunkier and less efficient, when you could have fixed your bug by doing the shift *before* the add. Or for example `lea 1(%rax, %rax), %eax` to shift-and-add in one instruction. Of course going 1 bit at a time is pointless anyway) – Peter Cordes Sep 25 '20 at 04:51
  • @PeterCordes thanks for pointing that out -- yea I was curious about how to do the first shift-left which seemed pretty clunky/confusing for me. – samuelbrody1249 Sep 25 '20 at 04:54

1 Answers1

3

A useful mathematical fact is that a value with N low-order 1 bits is 1 less than a power of two, which you can get by shifting. So you can simply load the count into %cl and do

mov $1, %eax
shl %cl, %eax
dec %eax

Of course if the count N is a constant known at assembly time, then let the assembler do the math and just load the result:

mov $((1 << N) - 1), %eax
Nate Eldredge
  • 48,811
  • 6
  • 54
  • 82
  • That's so cool, thanks for the clear explanation. Does `$((1 << N) - 1)` work in gas, or what assembler is that? – samuelbrody1249 Sep 25 '20 at 04:17
  • 1
    @samuelbrody1249: Yes, gas understands arithmetic on integer constants using C-like syntax. See https://sourceware.org/binutils/docs/as/Integer-Exprs.html#Integer-Exprs – Nate Eldredge Sep 25 '20 at 04:19
  • 1
    @NateEldredge: a more efficient way (on Intel at least) to create `2^N` for runtime-variable N is `xor %eax,%eax` / `bts %ecx, %eax`. Then yes, `dec` that. It fails for N=32, producing 0 instead of 0xFFFFFFFF, same as your shift method, but otherwise is identical. AMD might actually do better with mov-immediate / shl if your shift count happens to already be in ECX. – Peter Cordes Sep 25 '20 at 04:22
  • @NateEldredge got it, thank you. Are there other numbers like `2^n` where the result can be calculated with a sort of trick? – samuelbrody1249 Sep 25 '20 at 04:46
  • @samuelbrody1249: Powers of 2 are special because computers store numbers in binary. Related: https://catonmat.net/low-level-bit-hacks - you can do a lot of neat stuff with carry or borrow propagation through a contiguous group of 1 or 0 bits (respectively). – Peter Cordes Sep 25 '20 at 05:57
  • 1
    @NateEldredge: The book "Hacker's Delight" discusses some integer tricks. – W. Chang Sep 25 '20 at 12:45
  • `or $-1, %eax` `shl %cl, %eax` `not %eax` is another way to do it and produces shorter code. – W. Chang Sep 25 '20 at 12:50
  • note that this only works if cl < 32. To make it work for any values <= 32 see [Creating a mask with N least significant bits set](https://stackoverflow.com/q/52573447/995714) – phuclv Sep 26 '20 at 01:17