[討論] template bitcount 重用性問題

[EdisonX (卡卡獸)]

標題有點難想 , 見諒 , 小細節的問題也有點多 , 請海函。

首先我寫了份 bitwise - bitcount 函式 , 做成 template

最初版是寫成這樣

template<typename T> inline
size_t bitcount(T v) // slow but generation
{
    size_t c ;
    for(c = 0 ; v &= v - 1; ++c) ;
    return c;
}

鑑於效能 , 接著對每種 pod type 做特偏化

template<> inline size_t bitcount(unsigned char  v) {}
template<> inline size_t bitcount(unsigned short v) {}
template<> inline size_t bitcount(unsigned int   v) {}
template<> inline size_t bitcount(unsigned long  v) {}
template<> inline size_t bitcount(unsigned long long v) {}

接著我再回到最原始版的 template , 打算根據 bytes 數去呼叫不同版本的 bitcount
同時想考慮可能有超過 8 bytes 的情況 , 像是 non-padding struct 或 array
可能會用到

template<typename T> inline
size_t bitcount(T v)
{
    size_t icount = 0;
    switch( size_t ibytes = sizeof(T) )
    {
        case 8  : return bitcount<unsigned char > (v) ;
        case 4  : return bitcount<unsigned int  > (v) ;
        case 2  : return bitcount<unsigned short> (v) ;
        case 1  : return bitcount<unsigned long long> (v) ;
        default :

             // 一次處理 4 bytes
             unsigned int * puint  = (unsigned *) & v;
             for(size_t itimes = 0 ; itimes < ibytes / 4 ; ++itimes)
                icount+=bitcount<unsigned int>( * puint ++);

             // 剩下沒處理完的逐一 byte 處理
             unsigned char * pchar = (unsigned char *) puint ;
             for(size_t itimes = 0; itimes < ibytes % 4 ; ++itimes)
                icount+=bitcount<unsigned char>( *pchar++);
    }
    return icount ;
}

東西是做出來了沒錯，但截至目前為止有幾個問題想請教。

1. 資料型態問題

   先拿另一份 code 來講

   template<typename T>
   T mask_low_nbits(T v , int n)
   {
       T msk = (1 << n) - 1 ; // 這個有問題
       return v & msk ;
   }

   (1.1) 上面這段在 unsigned long long 時會出包，一般這情況會怎寫？
　　　　 T v = (1ULL << n) - 1 ;
         T v = (static_cast<T>(1) << n) - 1 ;
         或是有比較建議的方法嗎？

   (1.2) 上面的 T , 請問有沒有辦法判斷傳進來的是 unsigned type ?
         目前我找不到相關資料說明 (雖然我覺得不太可能辦到)

2. 自動展開 

   最終的  template<typename T> size_t bitcount(T v) ; 在非特定 bytes
   數下，我是用 for loop 展開，想請問有沒有類似以下的想法讓 template
   幫我自己展開 ? ( compile error .. )

   template<typename T , size_t nbytes = sizeof(T)>
   size_t bitcount(T v)
   {
         if(nbytes > 4) {
            return
               bitcount<unsigned> ( v )
             + bitcount<unsigned , nbytes-4 > ( *((unsigned*)& v + 1 ) ) ;
         }
         else if(nbytes) {
            return
              bitcount<unsigned char> ( v )
            + bitcount<unsigned char , nbytes-1> ( *( (unsigned char*) &v +1));
         }
   }


3. Resource

   (3.1) 另想知道有沒有文章或是書可以教一些這方面的技巧？

   (3.2) 我用 VS 寫 template 的時候，發現 keyin source code ，
      　 IDE 在做 template tips 時， " 好像 " 會比較 lag  ,
         請問是我的心理因素 , 還是也有人會這樣 ?

----

  以上 ， 問題雖有點贅述，應表達得還算清楚，在此先謝謝各位耐心看完，
  及不吝的回答，謝謝各位。

--
 「自從我學了 C#   , 人都變聰明 , 考試都考一百分」
 「自從我學了 VB   , 皮膚都變好 , 人也變漂亮了  」
 「自從我學了 Java , 明顯變壯   , 個子也變高了  」
 「自從我學了 C++  , 內分泌失調 , 頭都禿了...   」
                                          < Kuso 星爺語錄 >

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.169.158
※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1438966909.A.3D7.html
推 QQ29: 題外話, 為啥我inline template<> compile不過阿?
→ QQ29: 另外 其他function 為啥要加template<> 不加不是也可嗎?
→ EdisonX: 嗯 ... 因為我寫反了 @@ template<> inline  才對
→ EdisonX: 至於 template<> 不加的話那不就乾脆不要用 template 就
→ EdisonX:  好了 ? 你先查一下 template 特化吧
※ 編輯: EdisonX (123.195.169.158), 08/08/2015 01:49:00
→ QQ29: 不, 我意思是 這種特化 跟 不加 在這情況 不是根本一樣嗎@@
→ EdisonX: 大部份的情況下 , 特化的 template<> 可以拿掉無誤 , 只
→ EdisonX: 有少數一定要加 , 看情況而定
→ EdisonX:  而我最終的問題是用 template 有沒辦法把裡面的 for 拿
→ EdisonX:  掉 , 所以很自然全都弄成特化
→ Feis: 1.2: is_unsigned, 其他的部分我覺得這函式怪怪的 QQ
→ Feis: 1.1: T(1) 這種用法好像也蠻常見的?
推 kevingwn: 1.2和2都可以用enable_if<>的手法
→ Feis: 2: 我很少寫 TMP, 暴力展開: https://goo.gl/FK89a7
→ kevingwn: template<
→ Feis: 只是這種硬轉成 unsigned int * 的可靠度不知道怎樣
→ kevingwn:     typename T,
→ kevingwn:     typename = enable_if_t<is_unsigned<T>::value>
→ kevingwn: > T mask_low_nbits(T v , int n) { ... }
→ kevingwn: 2太多了,貼到 http://ideone.com/8Yp3YQ
→ EdisonX:  @Feis , 您給的 code 我 run 會無限展開造成 stack ov.
→ EdisonX:  @kevingwn , 這方法可行 , 唯我想試試是否呼叫直接寫
→ EdisonX:   bitcount(0x0123456789abcdefULL) 就可完成
推 azureblaze: 2. constexpr function 比TMP好讀好寫太多了
→ Feis: EdisonX: 我不確定發生甚麼事. 你餵的格式或 Compiler ?
→ Feis: ideone 上是可以跑. http://ideone.com/QDtuqB
→ EdisonX: @Feis:抱歉,我發現是我把 size_t bitcount(unsigned int)
→ EdisonX: 造成的 OV , 放回去就行了 , 謝謝您給的參考！
→ Feis: azureblaze: constexpr 要回傳值在編譯期算出才有用
→ Feis: 這邊比較像是函式生成.