{"id":24203,"date":"2022-12-01T03:12:13","date_gmt":"2022-11-30T21:42:13","guid":{"rendered":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/"},"modified":"2022-12-01T03:12:13","modified_gmt":"2022-11-30T21:42:13","slug":"solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise","status":"publish","type":"post","link":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/","title":{"rendered":"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise"},"content":{"rendered":"

[ad_1]
\n<\/p>\n

\n
\n
<\/div>\n
\n
\n

It turns out there is a general solution, which does not depend on word size, or even on two’s complement arithmetic. Here it is:<\/p>\n

int is_zero(int x)\n{\n    unsigned    y   = x;\n    unsigned    c0  = y^y;\n    unsigned    c1  = ~(~c0 + ~c0);\n    unsigned    c1h = ~c0 ^ (~c0 >> c1);\n    unsigned    y2  = y + ~c0;\n    unsigned    t1  = y ^ y2;\n    unsigned    t2  = t1 & y2;\n    unsigned    s   = t2 & c1h;\n    int         r   = s >> c1;\n\n    return r;\n}\n<\/code><\/pre>\n
Note that everything is done in unsigned, which is necessary to avoid overflow issues, and also to force the right shift to zero-fill.  I left the argument and return value as signed ints, with the first and last assignments simply changing the signed\/unsigned behavior (the final shift is only present to avoid overflow – see the comment below).<\/p>\n
The solution is actually pretty straightforward.  As has been noted, constant generation is trivial.  Zero is obtained by xor-ing something with itself.  All 1’s is the bitwise complement of that.  One is all 1’s xor’d with all 1’s shifted left one.<\/p>\n
So far this is all pretty trivial.  The tricky part is to get it to work regardless of word size.  To do this, it constructs a value whose high-order bit is 0 if x is non-zero, and 1 if x is zero.  It then masks this with a constant which is a single 1 in the high-order bit position, which is constructed from all 1’s xor’d with all 1’s shifted right 1.  The shift is guaranteed to zero-fill (rather than sign-extend) since the value is unsigned.<\/p>\n
Note that s<\/code> is either zero or a one in the high-order bit position.  The final return value, r<\/code>, shifts s<\/code> right by one in order to avoid overflow when assigning back to a signed integer.  This fix was suggested by Paul Hankin.  This makes the final return value either zero or else zero followed by one followed by all zeros.<\/p>\n
If you want to avoid the implicit conversions between signed and unsigned at the beginning and end of the function, you can use a union to alias the values:<\/p>\n
int is_zero(int x)\n{\n    union {int s; unsigned u;} su;\n    su.s = x;\n    unsigned    y   = su.u;\n    unsigned    c0  = y^y;\n    unsigned    c1  = ~(~c0 + ~c0);\n    unsigned    c1h = ~c0 ^ (~c0 >> c1);\n    unsigned    y2  = y + ~c0;\n    unsigned    t1  = y ^ y2;\n    unsigned    t2  = t1 & y2;\n    unsigned    s   = t2 & c1h;\n    su.u = s;\n    int         r = su.s;\n\n    return r;\n}\n<\/code><\/pre>\n
In this case, the final shift of s<\/code> is unnecessary, and the return value is either zero or else one followed by all zeros.  Note that the C90 standard doesn’t allow mixed code and declarations, so if that’s an issue, you would have to separate the declarations from the assignments, but the net result would be the same.<\/p>\n<\/p><\/div>\n
<\/div>\n<\/div>\n
            5<\/span> <\/p><\/div>\n<\/div>\n
[ad_2]<\/p>\n
solved Bit manipulation, return 0 if x != 0, or nonzero otherwise <\/p>\n","protected":false},"excerpt":{"rendered":"
[ad_1] It turns out there is a general solution, which does not depend on word size, or even on two’s complement arithmetic. Here it is: int is_zero(int x) { unsigned y = x; unsigned c0 = y^y; unsigned c1 = ~(~c0 + ~c0); unsigned c1h = ~c0 ^ (~c0 >> c1); unsigned y2 = y … Read more<\/a><\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[320],"tags":[2907,324],"class_list":["post-24203","post","type-post","status-publish","format-standard","hentry","category-solved","tag-bitwise-operators","tag-c"],"yoast_head":"\n[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise - JassWeb<\/title>\n<meta name=\"robots\" content=\"index, follow, max-snippet:-1, max-image-preview:large, max-video-preview:-1\" \/>\n<link rel=\"canonical\" href=\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\" \/>\n<meta property=\"og:locale\" content=\"en_US\" \/>\n<meta property=\"og:type\" content=\"article\" \/>\n<meta property=\"og:title\" content=\"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise - JassWeb\" \/>\n<meta property=\"og:description\" content=\"[ad_1] It turns out there is a general solution, which does not depend on word size, or even on two’s complement arithmetic. Here it is: int is_zero(int x) { unsigned y = x; unsigned c0 = y^y; unsigned c1 = ~(~c0 + ~c0); unsigned c1h = ~c0 ^ (~c0 >> c1); unsigned y2 = y ... Read more\" \/>\n<meta property=\"og:url\" content=\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\" \/>\n<meta property=\"og:site_name\" content=\"JassWeb\" \/>\n<meta property=\"article:published_time\" content=\"2022-11-30T21:42:13+00:00\" \/>\n<meta name=\"author\" content=\"Kirat\" \/>\n<meta name=\"twitter:card\" content=\"summary_large_image\" \/>\n<meta name=\"twitter:label1\" content=\"Written by\" \/>\n\t<meta name=\"twitter:data1\" content=\"Kirat\" \/>\n\t<meta name=\"twitter:label2\" content=\"Est. reading time\" \/>\n\t<meta name=\"twitter:data2\" content=\"2 minutes\" \/>\n<script type=\"application\/ld+json\" class=\"yoast-schema-graph\">{\"@context\":\"https:\/\/schema.org\",\"@graph\":[{\"@type\":\"Article\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/#article\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\"},\"author\":{\"name\":\"Kirat\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\"},\"headline\":\"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise\",\"datePublished\":\"2022-11-30T21:42:13+00:00\",\"mainEntityOfPage\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\"},\"wordCount\":375,\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"keywords\":[\"bitwise-operators\",\"c++\"],\"articleSection\":[\"Solved\"],\"inLanguage\":\"en-US\"},{\"@type\":\"WebPage\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\",\"url\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\",\"name\":\"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise - JassWeb\",\"isPartOf\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#website\"},\"datePublished\":\"2022-11-30T21:42:13+00:00\",\"breadcrumb\":{\"@id\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/#breadcrumb\"},\"inLanguage\":\"en-US\",\"potentialAction\":[{\"@type\":\"ReadAction\",\"target\":[\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/\"]}]},{\"@type\":\"BreadcrumbList\",\"@id\":\"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/#breadcrumb\",\"itemListElement\":[{\"@type\":\"ListItem\",\"position\":1,\"name\":\"Home\",\"item\":\"https:\/\/jassweb.com\/solved\/\"},{\"@type\":\"ListItem\",\"position\":2,\"name\":\"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise\"}]},{\"@type\":\"WebSite\",\"@id\":\"https:\/\/jassweb.com\/solved\/#website\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"name\":\"JassWeb\",\"description\":\"Build High-quality Websites\",\"publisher\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\"},\"potentialAction\":[{\"@type\":\"SearchAction\",\"target\":{\"@type\":\"EntryPoint\",\"urlTemplate\":\"https:\/\/jassweb.com\/solved\/?s={search_term_string}\"},\"query-input\":{\"@type\":\"PropertyValueSpecification\",\"valueRequired\":true,\"valueName\":\"search_term_string\"}}],\"inLanguage\":\"en-US\"},{\"@type\":\"Organization\",\"@id\":\"https:\/\/jassweb.com\/solved\/#organization\",\"name\":\"Jass Web\",\"url\":\"https:\/\/jassweb.com\/solved\/\",\"logo\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\",\"url\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"contentUrl\":\"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png\",\"width\":693,\"height\":132,\"caption\":\"Jass Web\"},\"image\":{\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/\"}},{\"@type\":\"Person\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31\",\"name\":\"Kirat\",\"image\":{\"@type\":\"ImageObject\",\"inLanguage\":\"en-US\",\"@id\":\"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/\",\"url\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"contentUrl\":\"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586\",\"caption\":\"Kirat\"},\"sameAs\":[\"http:\/\/jassweb.com\"],\"url\":\"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/\"}]}<\/script>\n<!-- \/ Yoast SEO plugin. -->","yoast_head_json":{"title":"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise - JassWeb","robots":{"index":"index","follow":"follow","max-snippet":"max-snippet:-1","max-image-preview":"max-image-preview:large","max-video-preview":"max-video-preview:-1"},"canonical":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/","og_locale":"en_US","og_type":"article","og_title":"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise - JassWeb","og_description":"[ad_1] It turns out there is a general solution, which does not depend on word size, or even on two’s complement arithmetic. Here it is: int is_zero(int x) { unsigned y = x; unsigned c0 = y^y; unsigned c1 = ~(~c0 + ~c0); unsigned c1h = ~c0 ^ (~c0 >> c1); unsigned y2 = y ... Read more","og_url":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/","og_site_name":"JassWeb","article_published_time":"2022-11-30T21:42:13+00:00","author":"Kirat","twitter_card":"summary_large_image","twitter_misc":{"Written by":"Kirat","Est. reading time":"2 minutes"},"schema":{"@context":"https:\/\/schema.org","@graph":[{"@type":"Article","@id":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/#article","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/"},"author":{"name":"Kirat","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31"},"headline":"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise","datePublished":"2022-11-30T21:42:13+00:00","mainEntityOfPage":{"@id":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/"},"wordCount":375,"publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"keywords":["bitwise-operators","c++"],"articleSection":["Solved"],"inLanguage":"en-US"},{"@type":"WebPage","@id":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/","url":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/","name":"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise - JassWeb","isPartOf":{"@id":"https:\/\/jassweb.com\/solved\/#website"},"datePublished":"2022-11-30T21:42:13+00:00","breadcrumb":{"@id":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/#breadcrumb"},"inLanguage":"en-US","potentialAction":[{"@type":"ReadAction","target":["https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/"]}]},{"@type":"BreadcrumbList","@id":"https:\/\/jassweb.com\/solved\/solved-bit-manipulation-return-0-if-x-0-or-nonzero-otherwise\/#breadcrumb","itemListElement":[{"@type":"ListItem","position":1,"name":"Home","item":"https:\/\/jassweb.com\/solved\/"},{"@type":"ListItem","position":2,"name":"[Solved] Bit manipulation, return 0 if x != 0, or nonzero otherwise"}]},{"@type":"WebSite","@id":"https:\/\/jassweb.com\/solved\/#website","url":"https:\/\/jassweb.com\/solved\/","name":"JassWeb","description":"Build High-quality Websites","publisher":{"@id":"https:\/\/jassweb.com\/solved\/#organization"},"potentialAction":[{"@type":"SearchAction","target":{"@type":"EntryPoint","urlTemplate":"https:\/\/jassweb.com\/solved\/?s={search_term_string}"},"query-input":{"@type":"PropertyValueSpecification","valueRequired":true,"valueName":"search_term_string"}}],"inLanguage":"en-US"},{"@type":"Organization","@id":"https:\/\/jassweb.com\/solved\/#organization","name":"Jass Web","url":"https:\/\/jassweb.com\/solved\/","logo":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/","url":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","contentUrl":"https:\/\/jassweb.com\/wp-content\/uploads\/2021\/02\/jass-website-logo-1.png","width":693,"height":132,"caption":"Jass Web"},"image":{"@id":"https:\/\/jassweb.com\/solved\/#\/schema\/logo\/image\/"}},{"@type":"Person","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/65c9c7b7958150c0dc8371fa35dd7c31","name":"Kirat","image":{"@type":"ImageObject","inLanguage":"en-US","@id":"https:\/\/jassweb.com\/solved\/#\/schema\/person\/image\/","url":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","contentUrl":"https:\/\/jassweb.com\/solved\/wp-content\/litespeed\/avatar\/1261af3c9451399fa1336d28b98ea3bb.jpg?ver=1776403586","caption":"Kirat"},"sameAs":["http:\/\/jassweb.com"],"url":"https:\/\/jassweb.com\/solved\/author\/jaspritsinghghumangmail-com\/"}]}},"_links":{"self":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/24203","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/comments?post=24203"}],"version-history":[{"count":0,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/posts\/24203\/revisions"}],"wp:attachment":[{"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/media?parent=24203"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/categories?post=24203"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/jassweb.com\/solved\/wp-json\/wp\/v2\/tags?post=24203"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}