Detail of message

Online Judge

Problem Set

Authors

Online Contests

User

Web Board
Home Page
F.A.Qs
Statistical Charts

Current Contest
Past Contests
Scheduled Contests
Award Contest

如果用k表示n这个数用二进制下末尾0的个数，那么n&(-n)=2^k；

Posted by 0810311106 at 2010-08-04 20:49:18 on Problem 2309 and last updated at 2010-08-04 21:04:01
In Reply To:temp = n & -n; 是啥意思呀？？？ Posted by:zsc08_wangqiang at 2010-08-02 15:58:26

在树状数组里，这2的k次方指的是c[n]它所在子树的叶子结点的个数，
你看图中12这个结点，12&（-12）=4，而且刚好12这个子树的叶子结点数为4，那么如果把
12-4+1的话，刚好就是9，12+4-1的话，就是15.那么对于任意一个数n有如下规律：
      min=n-n&(-n)+1
     max=n+n&(-n)-1
如果想彻底弄明白这个的话，建议去详细了解一下树状数组，它有时候用处很大的，特别是求数列前n项和（多维的也行）。

Followed by:

Re:如果用k表示n这个数用二进制下末尾0的个数，那么n&(-n)=2^k； (243) maxh123ok1 2011-07-22 09:51:40

Post your reply here:

Home Page Go Back To top