如何进一步优化计算整数平方根的C++函数？

我的算法中大部分时间消耗在调用<cmath>库的sqrt函数上，但我只需要整数平方根的整数部分，因此基于二进制手动开方实现了以下快速计算函数，同时还能判断输入是否为完全平方数：

const int BITLEN = sizeof(unsigned int) * 8;
bool DUMMYBOOL;

// digit in base 4 (two bits) starting at bit position i in n
inline int digit(unsigned int n, int i)
{
    return (n >> (BITLEN - i - 2)) & 3;
}

inline int isqrt(unsigned int n, bool* isSquare = &DUMMYBOOL)
{
    int answer = 0;
    int remaining = 0;
    
    for (int i = 0; i < BITLEN; i += 2)
    {
        remaining = (remaining << 2) + digit(n,i);

        answer <<= 1;
        int correction = (answer << 1) + 1;
        if (correction <= remaining)
        {
            remaining -= correction;
            answer++;
        }
    }
    *isSquare = remaining == 0;
    return answer;
}

已知x86_64架构下GCC编译的内置sqrt由硬件实现，速度难以超越，但我想知道该函数是否还有优化空间。之前尝试用__builtin_clz根据n的大小调整循环次数，反而降低了速度，我的数据平均为24位左右。

优化方向： #

• 内联digit函数逻辑，消除函数调用开销
  直接把digit(n,i)的计算逻辑写到循环体内，避免函数调用的间接开销，去掉单独的digit函数：

  remaining = (remaining << 2) + ((n >> (BITLEN - i - 2)) & 3);
  

• 改用无符号类型存储中间值
  将answer和remaining的类型从int改为unsigned int，避免符号位运算带来的额外开销，更符合数值的无符号特性：

  unsigned int answer = 0;
  unsigned int remaining = 0;
  

• 移除全局DUMMYBOOL，改用空指针默认参数
  全局变量可能引入缓存或优化限制，改为判断指针是否为空再赋值：

  inline unsigned int isqrt(unsigned int n, bool* isSquare = nullptr)
  {
      // ... 循环逻辑 ...
      if (isSquare != nullptr) {
          *isSquare = (remaining == 0);
      }
      return answer;
  }
  

• 跳过无效高位循环，减少迭代次数
  针对平均24位的输入，通过范围判断减少循环次数，利用分支预测优化：

  inline unsigned int isqrt(unsigned int n, bool* isSquare = nullptr)
  {
      unsigned int answer = 0;
      unsigned int remaining = 0;
      int start_i = 0;
      
      // 跳过前4组（8位）的无效循环，适配24位左右的输入
      if (n < (1U << 24)) {
          start_i = 8;
      }
      
      for (int i = start_i; i < BITLEN; i += 2)
      {
          remaining = (remaining << 2) + ((n >> (BITLEN - i - 2)) & 3);
          answer <<= 1;
          unsigned int correction = (answer << 1) + 1;
          if (correction <= remaining)
          {
              remaining -= correction;
              answer++;
          }
      }
      
      if (isSquare != nullptr) {
          *isSquare = (remaining == 0);
      }
      return answer;
  }
  

  这种方式避免了__builtin_clz的开销，同时利用分支预测（大部分输入命中n < (1U<<24)分支）减少循环次数。

• 手动展开循环，降低循环控制开销
  对于固定的循环次数（比如优化后12次），可以手动展开循环，减少循环变量的增减和判断开销，也可以添加#pragma GCC unroll让编译器自动展开循环。

内容的提问来源于stack exchange，提问作者doetoe