posts - 23,  comments - 1,  trackbacks - 0

Bitwise Operations

It's fairly convoluted though very efficient to encode lots of pieces of Boolean information into a single integer variable. Normal arithmetic and logical operations on such integer variables become unintuitive since we're not usually concerned with the value of the variables (e.g., 17) but rather with the status of individual bits (say, the first and fifth bits are set, all other bits are unset).

This page presents some bitwise operations I found useful while writing an extremely CPU-intensive ray-tracer. C syntax is used but the techniques can be applied to other languages including Java, often with only minor syntax changes.

Tests

  • Is a power of two:

        v & (v-1) == 0


  • Has two or more set bits:

        v & (v-1) > 0


  • Has exactly one set bit:

        v && (v & (v-1) == 0) == true


  • Has all specified bits set:

        v & bits == bits


  • Has at least one specified bit set:

        v & bits > 0


Operations

  • Toggle specific bits:

        v ^= b;


  • Set a bit:

        v |= b;


  • Unset a bit:

        v &= ~b;


  • Unset all bits apart from lowest set bit:

        ((v ^ (v-1)) + 1) >> 1


  • Unset the lowest set bit only:

        v &= (v-1)


Other

  • Count number of set bits:

        int n = 0; if (v) do { n++; } while (v &= (v-1)); return(n);


  • Compute log2 of a power of two:

        float x=v; return (*(int*)&x >> 23) - 127;


  • Compute minimum of two signed 32-bit integers:

        j + (((i-j) >> 31) & (i-j))

posted on 2007-05-18 09:29 yongqing 阅读(134) 评论(0)  编辑 收藏 引用 所属分类: optimization
只有注册用户登录后才能发表评论。

<2007年5月>
293012345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(1)

随笔分类

随笔档案

文章分类

收藏夹

blog

linux

storage

windows

搜索

  •  

最新评论

阅读排行榜

评论排行榜