0
\$\begingroup\$

The following C# methods take n bits and operates on them all in one pass.

// Sets n bits to zero at index i.
uint zerobits(uint x, int n, int i) {
    return x & ~((uint.MaxValue >> (sizeof(uint) * 8 - n)) << i);
}

// Sets n bits to one at index i.
uint setbits(uint x, int n, int i) {
    return x | ((uint.MaxValue >> (sizeof(uint) * 8 - n)) << i);
}

// Toggles n bits at index i.
uint togglebits(uint x, int n, int i) {
    return x ^ ((uint.MaxValue >> (sizeof(uint) * 8 - n)) << i);
}

Is there any way to optimize these? Or do they not need to be optimized at all?

\$\endgroup\$
  • 4
    \$\begingroup\$ I don't know about optimizing, but you could certainly extract the common logic out. Beyond that, I'm curious about the larger context and problem you're trying to solve. \$\endgroup\$ – RubberDuck Dec 7 '15 at 1:09
  • 5
    \$\begingroup\$ "Or do they not need to be optimized at all?" That's a question you will have to answer for yourself. Is this performance-sensitive code? Does this code meet your performance requirements? \$\endgroup\$ – svick Dec 7 '15 at 16:13
  • \$\begingroup\$ @svick I mean, do they need to be optimized--if they're actually inefficient. It does meet my requirements, but faster is better regardless. \$\endgroup\$ – FatalSleep Dec 8 '15 at 9:07
  • 1
    \$\begingroup\$ It's not clear what it is that you're really trying to accomplish here. Yes, I know that you want to minimize your storage space, but we've no idea why. Without that information, I don't think anyone can provide a meaningful review. As far as performance, you'll need to profile your code to determine is this is even a bottleneck and worth trying to optimize at all. Hint: Only 20% of your code causes 80% of the performance issues. It's unlikely this is the 20. To find the 20, you have to measure. \$\endgroup\$ – RubberDuck Dec 8 '15 at 9:31
  • 1
    \$\begingroup\$ I think what he is asking is clear. Can these be made faster? More efficient? \$\endgroup\$ – Oguz Ozgul Dec 8 '15 at 13:34
1
\$\begingroup\$

The following is the IL generated for zerobits(uint x, int n, int i);

There seems to be full optimization by inlining sizeof(uint) * 8 = 32, and uint.MaxValue = -1 = 0xffffffff

The CIL runtime stack works only with 4 byte or 8 byte integers, even the LDC_I4_S pushes a byte as a 4 byte integer to the stack, so, there is no performance gain in changing parameter types to smaller integers, byte or short

A slight improvement (may be);

These methods need not to be instance members and can be defined static. Changing them to static will remove 1 push instruction to the stack (argument 0, the instance to invoke the method on) at the caller site.

That's all. 100 million iterations on my 2-cpu 8 core windows 7 HP machine executes in 17-18 ms, and 8-9 ms of it seems to be the iteration (empty loop) itself.

IL_0000:  ldarg.1       // push x (stack : x)
IL_0001:  ldc.i4.m1     // push 0xffffffff (uint.MaxValue is inlined, m1 = -1 = 0xffffffff) (stack : x, 0xffffffff)
IL_0002:  ldc.i4.s   32 // push 0x20 (sizeof(uint) * 8 is inlined) (stack: x, 0xffffffff, 0x20)
IL_0004:  ldarg.2       // push n (stack: x, 0xffffffff, 0x20, n)

IL_0005:  sub           // subtract -> (0x20 - n) (stack : x, 0xffffffff, 0x20-n)

// The following two instructions are for ENSURING SHIFTING RIGHT WITH A POSITIVE INTEGER
IL_0006:  ldc.i4.s   31 // push 0x1f (stack : x, 0xffffffff, 0x20-n, 0x1f)
IL_0008:  and           // (0x20 - n) & 0x1f (stack : x, 0xffffffff, 0x20-n) - We assume that n < 0x20

IL_0009:  shr.un        // shift right unsigned, 0xffffffff >> (0x20-n) (stack : x, 0xffffffff >> (0x20-n))

IL_000a:  ldarg.3       // push i (stack : x, 0xffffffff >> (0x20-n), i)

// The following two instructions are for ENSURING SHIFTING LEFT WITH A POSITIVE INTEGER
IL_000b:  ldc.i4.s   31 // push 0x1f (stack : x, 0xffffffff >> (0x20-n), i, 0x1f)
IL_000d:  and           // (i & 0x1f) (stack : x, 0xffffffff >> (0x20-n), i) - We assume that i < 0x20

IL_000e:  shl           // shift left (0x20-n) << i (stack : x, (0xffffffff >> (0x20-n)) << i)
IL_000f:  not           // not (stack : x, ~(0xffffffff >> (0x20-n)) << i))
IL_0010:  and           // and x & ~(0xffffffff >> (0x20-n)) << i) (stack : x & ~((0xffffffff >> (0x20-n)) << i)
IL_0011:  ret           // return x & ~(0xffffffff >> (0x20-n)) << i) 
\$\endgroup\$

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