编程小贴士

给你的编程提供小点子


快速判断一个32位的字中是否存在值为”0″的byte

首先为什么要做这样的判断呢?

当你要strcpy或者strcmp或者hash一个字符串的时候,传统的方法是每个byte进行比较。以strcpy为例,当一个字符串 比较长,我们用32(或者64位)的字长进行copy的话,一次拷贝会拷贝4个byte,能节省很多时间(忽略内存对齐等情况)。

但是,使用32位的字长进行拷贝一个难点就是判断字符串的结尾,因为字符串长度不一定是4的整数倍,每次从内存中取4个byte,我们需要判断这4个byte中是否有某个byte是0,从而判断字符串是否结束。

最传统的做法就是对每个字节进行一次判断,或者将所有字节乘起来,看结果是否是0:http://www.spongeliu.com/

unsigned char * p = (unsigned char *) & v;  
bool hasNoZeroByte = *p && *(p + 1) && *(p + 2) && *(p + 3);

上面的代码需要12步操作,并且需要若干乘指令,效率不高。

一种传统有效的方法是通过对每个byte进行一次掩码的操作来判断是否存在0:

bool hasNoZeroByte = ((v & 0xff) && (v & 0xff00) && (v & 0xff0000) && (v & 0xff000000));

上面的操作相当于取出每一个byte,并进行与操作,最终判断是否是0,这样做需要进行7次操作。

那么,是否有更快的方法呢? 看下面的表达式:

unsigned int v; // 32-bit word to check if any 8-bit byte in it is 0
bool hasZeroByte = ~((((v & 0x7F7F7F7F) + 0x7F7F7F7F) | v) | 0x7F7F7F7F);

这种方法进行了5次操作来完成整个工作!具体是怎么做到的,让我们仔细来看:

首先,将v同 0x7f7f7f7f 进行&操作,目的是将v中每个byte的最高位清零;

然后,再加上 0x7f7f7f7f 的目的是让每个byte的低7位溢出,这个时候只要每个byte的低7位不全是0,那么就会溢出;

随后,我们再将得到的数同原先的v进行一个“按位或”的操作,这样每个byte的最高位都会被置为1,除非这个byte初始为0(若初始为0,则第二步的时候不会溢出,第三步的时候0|0还是0);

再然后,我们再讲得到的数同 0x7f7f7f7f “按位或”,则如果初始的数不包含0byte,我们就会得到0xffffffff,否则我们得不到这个数;

最后,进行一个“按位否”操作,就会得到一个0或者非0。

我们用两个例子来更直观的说明,先举一个不包含0byte的32位数,以 0x5FF23D6E 为例:

0x5FF23D6E & 0x7F7F7F7F = 0x5f723d6e;  //每个byte的高位全清0
0x5f723d6e + 0x7F7F7F7F = 0xdef1bced; //对每个byte的低7位进行溢出,只有当一个byte是0或者是“10000000”的时候不会溢出
0xdef1bced | 0x5FF23D6E = 0xdff3bdef; //或上原来的数,这是除非一个byte初始是0,否则最高位都会是1
0xdff3bdef | 0x7F7F7F7F = 0xffffffff; //将所有bit置为1
~ 0xffffffff = 0; //得到结果

再使用一个包含0byte的32位数为例,以 0x5FF2006E 为例:

0x5FF2006E & 0x7F7F7F7F = 0x5f72006e;  //每个byte的高位全清0
0x5f72006e + 0x7F7F7F7F = 0xdef17fed; //对每个byte的低7位进行溢出,这个时候因为第三个byte是0,所以这个byte的最高位不是1
0xdef17fed | 0x5FF2006E = 0xdff37fef; //或上原来的数,第三个byte最高位不是1
0xdff37fef | 0x7F7F7F7F = 0xffff7fff; //第三个byte最高位不是1,其他所有位都是1
~ 0xffff7fff = 0x8000; //得到结果

这种方法在一些字符串操作的性能优化,尤其是当大量字符串需要被哈希、拷贝时还是比较有效的。

212 Responses to “ 快速判断一个32位的字中是否存在值为”0″的byte ”

  1. Great info. Lucky me I found your blog by chance (stumbleupon).
    I have saved it for later!

  2. I was able to find good advice from your blog articles.

  3. I am so grateful for your article.Really thank you! Really Cool.

  4. best pron说道:

    u2l2tq You have made some decent points there. I looked on the internet to learn more about the issue and found most people will go along with your views on this web site.

  5. I really liked your article.Really thank you! Really Great.

  6. large anal plugs说道:

    Hey, thanks for the blog article.Really thank you! Awesome.

  7. Appreciate you sharing, great blog post.Much thanks again.

  8. see pron说道:

    Q8vp1Z I surely did not realize that. Learnt a thing new nowadays! Thanks for that.

  9. wow, awesome article.Thanks Again. Fantastic.

  10. Major thanks for the blog.Really thank you! Awesome.

  11. Really appreciate you sharing this blog article.Thanks Again.

  12. A big thank you for your post.Really looking forward to read more. Much obliged.

  13. girl coloring说道:

    Thanks again for the blog article.Really looking forward to read more. Will read on

  14. Mca reviews说道:

    You know so much its almost tough to argue with you (not that I personally

  15. we could greatly benefit from each other. If you are interested feel free

  16. Im thankful for the article.Really looking forward to read more. Awesome.

  17. Right now it looks like WordPress is the best blogging platform out

  18. of him as nobody else know such designated about my trouble.

  19. Very good blog article.Thanks Again. Want more.

  20. Wow, what a video it is! In fact good feature video, the lesson given in this video is in fact informative.

  21. Oluwadamilare说道:

    I’а†ve recently started a web site, the info you provide on this site has helped me tremendously. Thank you for all of your time & work.

  22. Thanks a lot for the article.Much thanks again. Awesome.

  23. Very neat blog.Really thank you! Want more.

  24. casino betting说道:

    This info is invaluable. When can I find out more?

  25. buy cialis说道:

    Thanks again for the blog post.Much thanks again. Keep writing.

  26. Wow, great article post.Really thank you! Really Cool.

  27. online说道:

    I truly appreciate this post. I?аАТ’аЂа†ve been looking all over for this! Thank goodness I found it on Bing. You ave made my day! Thanks again

  28. adameve offer说道:

    I really enjoy the article post.Much thanks again. Awesome.

  29. Thanks for the good writeup. It in truth was once a entertainment account it.

  30. Right here is the right webpage for anybody who wishes to understand this topic.

  31. Merely wanna comment that you have a very nice internet site , I enjoy the style it actually stands out.

  32. I really like and appreciate your post.Much thanks again. Keep writing.

  33. I relish, result in I found exactly what I used to be looking for. You have ended my four day long hunt! God Bless you man. Have a great day. Bye

  34. Woking taxi说道:

    Ridiculous story there. What occurred after? Thanks!

  35. first time anal说道:

    Very neat article. Really Cool.

  36. stumbleupon everyday. It as always useful

  37. Wow that was unusual. I just wrote an really long comment but after I clicked submit my comment didn at show up. Grrrr well I am not writing all that over again. Anyway, just wanted to say great blog!

  38. mobile repair说道:

    Im grateful for the article.Thanks Again. Fantastic.

  39. status说道:

    Wow, fantastic blog layout! How long have you been blogging for? you made blogging look easy. The overall look of your site is fantastic, as well as the content!

  40. Very nice blog post. I certainly appreciate this site. Continue the good work!

  41. Thank you ever so for you article post.Thanks Again. Will read on

  42. PERM说道:

    Thanks-a-mundo for the article.Really looking forward to read more. Fantastic.

  43. Asuquo说道:

    This will be priced at perusing, I like the idea a lot. I am about to take care of your unique satisfied.

  44. Nwokolo说道:

    Wow! Thank you! I continually wanted to write on my blog something like that. Can I include a fragment of your post to my site?

  45. wow, awesome post.Much thanks again. Will read on…

  46. living large说道:

    Fantastic blog.Much thanks again. Cool.

  47. Very good blog article.Much thanks again.

  48. You got a very good website, Glad I observed it through yahoo.

  49. vibrator说道:

    A big thank you for your blog post. Want more.

  50. I truly appreciate this post. I have been looking all over for this! Thank God I found it on Google. You have made my day! Thanks again..

  51. This blog was how do you say it? Relevant!! Finally I have found something which helped me. Thank you!

  52. Merely wanna input that you have a very decent internet site , I like the style it actually stands out.

  53. lose weight说道:

    Thanks for sharing, this is a fantastic blog article.Really looking forward to read more. Want more.

  54. anal trainer说道:

    Appreciate you sharing, great blog post.Really thank you! Fantastic.

  55. lgbt sex toys说道:

    Very good blog article.Really looking forward to read more. Much obliged.

  56. sex gel说道:

    Fantastic post.Really thank you! Want more.

  57. sell说道:

    Great post.Really thank you! Cool.

  58. Homepage说道:

    Appreciate you sharing, great blog. Really Cool.

  59. Phone Recycle说道:

    I think this is a real great blog post.

  60. I really like and appreciate your blog.Thanks Again. Really Great.

  61. Very good blog post.Much thanks again.

  62. g-spot vibrators说道:

    wow, awesome article post.Really looking forward to read more. Cool.

  63. Nice blog here! Additionally your website loads up very fast! What web host are you the usage of? Can I get your associate link to your host? I want my website loaded up as fast as yours lol

  64. credits online说道:

    Wow, superb blog layout! How lengthy have you ever been blogging for?

  65. sim so dep说道:

    now. (from what I ave read) Is that what you are using

  66. Joi说道:

    Very informative post.Really thank you! Really Great.

  67. rating说道:

    This awesome blog is obviously interesting and informative. I have picked many handy stuff out of this source. I ad love to return again and again. Thanks a bunch!

  68. Thanks-a-mundo for the post.Thanks Again. Much obliged.

  69. Successful tips说道:

    Thanks again for the blog article.Really looking forward to read more.

  70. Thanks so much for the post.Thanks Again. Will read on…

  71. I really enjoy the blog. Will read on…

  72. Major thanks for the blog article.Really thank you! Cool.

  73. I value the post.Much thanks again.

  74. cbd说道:

    Thanks for the article post.Really thank you! Cool.

  75. visit website说道:

    Thanks for sharing, this is a fantastic article post.Thanks Again. Really Cool.

  76. coursework help说道:

    Thanks for sharing, this is a fantastic blog post.Really looking forward to read more.

  77. Thanks-a-mundo for the post.Really looking forward to read more. Fantastic.

  78. nonetheless, you command get bought an edginess over

  79. Very nice article. I certainly love this website. Continue the good work!

  80. Sisimiut说道:

    There are so many choices out there that I am completely confused.. Any tips? Thank you!

  81. try this说道:

    If you have any recommendations, please let me know. Thanks!

  82. red shoes说道:

    Really informative blog.Really thank you! Really Great.

  83. Thank you for some other wonderful post. Where else may anyone get that type of info in such a perfect means of writing? I ave a presentation subsequent week, and I am on the look for such info.

  84. Waec说道:

    You ave made some good points there. I checked on the net for more info about the issue and found most individuals will go along with your views on this web site.

  85. Waec expo说道:

    Usually I do not read article on blogs, but I wish to say that this write-up very forced me to check out and do it! Your writing taste has been amazed me. Thanks, quite great article.

  86. Yay google is my king helped me to find this great web site !.

  87. Kids watches说道:

    I appreciate you sharing this article post.Thanks Again. Much obliged.

  88. Hey, thanks for the blog post.Really thank you! Keep writing.

  89. Normally I do not learn article on blogs, however I would like to say that this write-up very compelled me to try and do so! Your writing taste has been amazed me. Thank you, quite great article.

  90. I appreciate you sharing this blog.Really thank you! Cool.

  91. baca disini说道:

    I am so grateful for your post.Really thank you! Awesome.

  92. elo boost说道:

    Really appreciate you sharing this blog article.Really thank you!

  93. Im obliged for the post.Really looking forward to read more. Awesome.

  94. Precisely what I was looking for, thanks for posting.

  95. Thanks-a-mundo for the post.Thanks Again.

  96. clit stimulator说道:

    Hey, thanks for the blog post. Awesome.

  97. Say, you got a nice blog article.Really thank you! Cool.

  98. I really liked your article.Really looking forward to read more. Will read on…

  99. Major thankies for the blog article. Keep writing.

  100. This webpage doesn at show up appropriately on my droid you may want to try and repair that

  101. Appreciate you sharing, great blog. Really Great.

  102. I\ ave been using iXpenseIt for the past two years. Great app with very regular updates.

  103. Pillows说道:

    I really enjoy the blog.Thanks Again. Cool.

  104. I truly appreciate this blog post.Really thank you! Keep writing.

  105. Some really prime blog posts on this internet site , saved to favorites.

  106. Wow, this post is pleasant, my younger sister is analyzing these kinds of things, thus I am going to tell her.

  107. This is a good tip especially to those fresh to the blogosphere. Short but very precise info Many thanks for sharing this one. A must read article!

  108. Incredible points. Great arguments. Keep up the great spirit.

  109. Wow, great blog post.Much thanks again. Want more.

  110. Haus on Handy说道:

    Im thankful for the article.Really thank you! Really Cool.

  111. What web host are you the use of? Can I get your associate hyperlink in your host?

  112. infinity说道:

    Really enjoyed this blog.Really looking forward to read more. Keep writing.

  113. manufacturer说道:

    This particular blog is no doubt educating and besides amusing. I have found a bunch of interesting things out of this amazing blog. I ad love to return again soon. Thanks!

  114. Everything is very open with a really clear explanation of the challenges. It was truly informative. Your website is very useful. Many thanks for sharing!

  115. I cannot thank you enough for the article post.Thanks Again. Keep writing.

  116. mjagkie okna说道:

    This excellent website truly has all of the information I needed about this subject and didn at know who to ask.

  117. Im obliged for the article.Much thanks again. Will read on

  118. Thanks so much for the article.Thanks Again. Will read on…

  119. Im obliged for the post.Really thank you! Want more.

  120. for more details说道:

    This excellent website truly has all the information I needed concerning this subject and didn at know who to ask.

  121. I loved your blog post.Really looking forward to read more. Keep writing.

  122. Luanna说道:

    It is really a great and helpful piece of info. I am glad that you shared this useful info with us. Please keep us informed like this. Thanks for sharing.

  123. whatsapp说道:

    It as another strong business for michael kors bags outlet. In

  124. Sosyal medya başarınızı kat ve kat artırmak, postlarınız ve hesaplarınızla Instagram başlıca gönderilerde yer almak için takipçi sayınızın çok yüksek olması

  125. Really enjoyed this article.Thanks Again. Keep writing.

  126. Tüm siparişlerinizde Anlık Teslimat ve 7/24 Destek 6 Yıllık sektörel tecrübemizle en iyi hizmeti sunuyoruz!

  127. Well I sincerely liked studying it. This tip provided by you is very constructive for correct planning.

  128. I value the blog post.Much thanks again. Cool.

  129. Simply wanna comment that you have a very decent site, I love the style it really stands out.

  130. This is one awesome blog post.

  131. go to see说道:

    wow, awesome post.Thanks Again. Much obliged.

  132. visit website说道:

    You made some really good points there. I looked on the web for additional information about the issue and found most people will go along with your views on this site.

  133. I loved your article.Thanks Again. Will read on…

  134. Thanks-a-mundo for the article post.Much thanks again. Want more.

  135. I really liked your blog article. Great.

  136. Enjoyed every bit of your blog post. Keep writing.

  137. Im obliged for the article post.Thanks Again. Really Cool.

  138. tankionline说道:

    Appreciate you sharing, great blog article.Thanks Again. Cool.

  139. I value the post.Thanks Again. Will read on…

  140. instagram takipçi satın almak说道:

    Son yılların en popüler uygulaması haline gelen Instagram, milyonlarca kullanıcıya hizmet vermektedir.

  141. I value the blog.Much thanks again. Will read on

  142. share说道:

    Thanks-a-mundo for the blog article.Much thanks again. Keep writing.

  143. twitter说道:

    Thanks for the article post.Much thanks again. Want more.

  144. novyj snegohod说道:

    I truly appreciate this blog post.Thanks Again. Will read on

  145. Just to let you know your webpage appears a little bit unusual in Firefox on my notebook with Linux.

  146. Diyp kozmetik说道:

    interest not fake then, about one hour in the

  147. A round of applause for your article. Awesome.

  148. xlxx porn说道:

    Hey, thanks for the blog post.Much thanks again.

  149. znakomstvafoto说道:

    I truly appreciate this blog article. Really Cool.

  150. Excellent article. I am dealing with a few of these issues as well..

  151. This is one awesome article.Really looking forward to read more. Much obliged.

  152. more info说道:

    Im thankful for the post.Thanks Again. Much obliged.

  153. click here说道:

    You made some clear points there. I looked on the internet for the issue and found most persons will go along with with your site.

  154. fyve derbyshires说道:

    Thanks for the article.Much thanks again. Keep writing.

  155. I view something really special in this internet site.

  156. this website说道:

    over it all at the minute but I have bookmarked it and also added your RSS

  157. Very good article! We will be linking to this particularly great article on our site. Keep up the good writing.

  158. Quick Divorce说道:

    Say, you got a nice blog post.Really looking forward to read more.

  159. Say, you got a nice blog article.Much thanks again. Fantastic.

  160. colorful dildos说道:

    Really informative blog post.Thanks Again. Really Great.

  161. Major thanks for the blog.Thanks Again. Really Cool.

  162. pleasure ring说道:

    Wow, great post.Really looking forward to read more. Really Cool.

  163. Thank you for your article post. Keep writing.

  164. This is one awesome blog. Much obliged.

  165. clickhere说道:

    very nice publish, i certainly love this website, carry on it

  166. 7 inch dildo说道:

    Really informative blog article.Really thank you! Awesome.

  167. Great blog.Much thanks again. Keep writing.

  168. bunny vibrator说道:

    Hey, thanks for the article post.Thanks Again.

  169. Keep up the superb piece of work, I read few posts on this website and I believe that your web site is really interesting and has got circles of superb information.

  170. official site说道:

    Way cool! Some extremely valid points! I appreciate you penning this post and also the rest of the website is extremely good.

  171. This is a topic that is near to my heart Thank you! Where are your contact details though?

  172. wow, awesome article post.Thanks Again. Really Great.

  173. We stumbled over here different page and thought I might as well check things out. I like what I see so now i am following you. Look forward to exploring your web page repeatedly.

  174. my portfolio说道:

    Thanks a lot for the blog. Keep writing.

  175. good morning说道:

    You have brought up a very great details , thanks for the post.

  176. Really enjoyed this article post.Really thank you! Awesome.

  177. or fashionable and useful, you will easily find your Id Nike Blazers sandals at a discount price to fit your budget.

  178. SharonElese说道:

    Perfect update of captcha recognition software “XEvil 4.0″:
    captchas regignizing of Google (ReCaptcha-2 and ReCaptcha-3), Facebook, BitFinex, Bing, Hotmail, SolveMedia, Yandex,
    and more than 8400 another subtypes of captcha,
    with highest precision (80..100%) and highest speed (100 img per second).
    You can use XEvil 4.0 with any most popular SEO/SMM software: iMacros, XRumer, GSA SER, ZennoPoster, Srapebox, Senuke, and more than 100 of other programms.

    Interested? There are a lot of introducing videos about XEvil in YouTube.

    Free XEvil Demo available.

    See you later!

  179. Simply wanna comment that you have a very decent site, I enjoy the layout it actually stands out.

  180. internet explorer crashing on launch How to build a wordpress site while domain is on redirect.?

  181. Game Online说道:

    I value the blog.Really looking forward to read more. Cool.

  182. Very nice article and straight to the point. I am not sure if this is in fact the best place to ask but do you folks have any ideea where to get some professional writers? Thx

  183. I think this is a real great blog post.Thanks Again. Fantastic. ventolin

  184. normanton park说道:

    Hey, I just thought of saying how good the information you have in this blog. There are some add on related reference to it. Refer to One Normanton Park or One Normanton Park Thank you for browsing

  185. normanton park说道:

    That’s cool, I just wanna commenting how excellent the information you have in this blog. There are some alternative related reference to it. Refer to One Normanton Park or One Normanton Park Thank you for visitng

  186. This Is The Technique That as Actually Enabling bag-professionals To Advance

  187. click here说道:

    I think other website proprietors should take this web site as an model, very clean and great user pleasant style and design.

  188. 12v nicd battery说道:

    Im grateful for the blog.Really thank you! Fantastic.

  189. live casino说道:

    I think other web site proprietors should take this site as an model, very clean and fantastic user genial style and design, as well as the content. You are an expert in this topic!

  190. hand craft说道:

    Thanks for some other excellent post. The place else may just anybody get that type of info in

  191. some truly wonderful information, Gladiolus I discovered this.

  192. I think this is a real great blog post.Much thanks again. Cool.

  193. techgearpage.com说道:

    This web site certainly has all of the information and facts I needed about this subject and didn at know who to ask.

  194. fluffy kitt说道:

    There is perceptibly a bunch to identify about this. I believe you made some good points in features also.

  195. bitcoin说道:

    paul smith ?? Listed Here Is A Solution That as Even Assisting bag-masters Grow

  196. Cabinet Painters说道:

    Im no pro, but I consider you just crafted a very good point point. You certainly know what youre talking about, and I can really get behind that. Thanks for staying so upfront and so truthful.

  197. This blog was how do you say it? Relevant!! Finally I ave found something that helped me. Many thanks!

  198. Davidliara说道:

    Выездной мобильный шиномонтаж в Москве и МО круглосуточно!
    Мегафон: +7(495)908-97-71
    Мтс: +7(915)448-25-25
    Хранение шин.
    1. Шиномонтажные работы.
    2. Снятие секреток.
    3. Переобувка шин.
    4. Ремонт проколов и порезов.
    Выездной шиномонтаж 24 часа в Москве и МО.
    Звоните!

  199. Say, you got a nice blog.Really thank you! Cool.

  200. I?ve recently started a blog, the info you offer on this site has helped me greatly. Thanks for all of your time & work.

  201. Thank you for your blog post.Really thank you! Cool.

  202. Heya i am for the first time here. I came across this board and I find It really useful & it helped me out much. I hope to give something back and aid others like you helped me.

  203. i love pron说道:

    4ORPJH Some really wonderful posts on this internet site, thankyou for contribution.

  204. They are added for the price in the house, deducted at the closing and paid directly towards the bank my website for example, if you might be in need for cash

  205. Alhambra realtor说道:

    Just to let you know your site appears a little bit different on Safari on my laptop using Linux.

  206. You got a very good website, Gladiola I noticed it through yahoo.

  207. Looking around I like to surf around the web, often I will just go to Digg and follow thru

  208. This is one awesome post.Really looking forward to read more. Want more.

  209. Very good blog post. I certainly love this site. Keep it up!

  210. What i discover troublesome is to find a weblog that may capture me for a minute however your blog is different. Bravo.

Leave a Reply

Your email address will not be published.

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>