{"id":26664,"date":"2017-12-22T19:54:15","date_gmt":"2017-12-22T14:24:15","guid":{"rendered":"https:\/\/www.wikitechy.com\/technology\/?p=26664"},"modified":"2017-12-22T19:54:15","modified_gmt":"2017-12-22T14:24:15","slug":"check-number-multiple-9-using-bitwise-operators","status":"publish","type":"post","link":"https:\/\/www.wikitechy.com\/technology\/check-number-multiple-9-using-bitwise-operators\/","title":{"rendered":"C++ Program Check if a number is multiple of 9 using bitwise operators"},"content":{"rendered":"

Given a number n, write a function that returns true if n is divisible by 9, else false. The most simple way to check for n\u2019s divisibility by 9 is to do n%9. <\/span>
\nAnother method is to sum the digits of n. If sum of digits is multiple of 9, then n is multiple of 9.
\nThe above methods are not bitwise operators based methods and require use of % and \/.
\nThe bitwise operators<\/a> are generally faster than modulo and division operators. Following is a bitwise operator based method to check divisibility by 9.<\/p>\n[pastacode lang=\u201dcpp\u201d manual=\u201d%23include%3Ciostream%3E%0Ausing%20namespace%20std%3B%0A%20%0A%2F%2F%20Bitwise%20operator%20based%20function%20to%20check%20divisibility%20by%209%0Abool%20isDivBy9(int%20n)%0A%7B%0A%20%20%20%20%2F%2F%20Base%20cases%0A%20%20%20%20if%20(n%20%3D%3D%200%20%7C%7C%20n%20%3D%3D%209)%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20if%20(n%20%3C%209)%0A%20%20%20%20%20%20%20%20return%20false%3B%0A%20%0A%20%20%20%20%2F%2F%20If%20n%20is%20greater%20than%209%2C%20then%20recur%20for%20%5Bfloor(n%2F9)%20-%20n%258%5D%0A%20%20%20%20return%20isDivBy9((int)(n%3E%3E3)%20-%20(int)(n%267))%3B%0A%7D%0A%20%0A%2F%2F%20Driver%20program%20to%20test%20above%20function%0Aint%20main()%0A%7B%0A%20%20%20%20%2F%2F%20Let%20us%20print%20all%20multiples%20of%209%20from%200%20to%20100%0A%20%20%20%20%2F%2F%20using%20above%20method%0A%20%20%20%20for%20(int%20i%20%3D%200%3B%20i%20%3C%20100%3B%20i%2B%2B)%0A%20%20%20%20%20%20%20if%20(isDivBy9(i))%0A%20%20%20%20%20%20%20%20%20cout%20%3C%3C%20i%20%3C%3C%20%22%20%22%3B%0A%20%20%20%20return%200%3B%0A%7D\u201d message=\u201dC programming\u201d highlight=\u201d\u201d provider=\u201dmanual\u201d\/]\n

Output:<\/strong><\/p>\n

0 9 18 27 36 45 54 63 72 81 90 99<\/pre>\n[ad type=\u201dbanner\u201d]\n
How does this work?<\/strong>
\nn\/9<\/em> can be written in terms of n\/8<\/em> using the following simple formula.<\/p>\n
n\/9 = n\/8 - n\/72<\/pre>\n
Since we need to use bitwise operators, we get the value of floor(n\/8) using n>>3 and get value of n%8 using n&7. We need to write above expression in terms of floor(n\/8) and n%8.
\nn\/8 is equal to \u201cfloor(n\/8) + (n%8)\/8\u201d. Let us write the above expression in terms of floor(n\/8) and n%8<\/p>\n
n\/9 = floor(n\/8) + (n%8)\/8 - [floor(n\/8) + (n%8)\/8]\/9\r\nn\/9 = floor(n\/8) - [floor(n\/8) - 9(n%8)\/8 + (n%8)\/8]\/9\r\nn\/9 = floor(n\/8) - [floor(n\/8) - n%8]\/9<\/pre>\n
From above equation, n is a multiple of 9 only if the expression floor(n\/8) \u2013 [floor(n\/8) \u2013 n%8]\/9 is an integer. This expression can only be an integer if the sub-expression [floor(n\/8) \u2013 n%8]\/9 is an integer. The subexpression can only be an integer if [floor(n\/8) \u2013 n%8] is a multiple of 9. So the problem reduces to a smaller value which can be written in terms of bitwise operators.<\/p>\n[ad type=\u201dbanner\u201d]\n","protected":false},"excerpt":{"rendered":"
Check if a number is multiple of 9 using bitwise operators – Bit Algorithm – Given a number n, write a function that returns true if n is divisible by 9.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[74852,83515,1],"tags":[79674,79671,79675,79665,79666,79669,79667,79668,79672,79676,79677,79673,79670],"class_list":["post-26664","post","type-post","status-publish","format-standard","hentry","category-bit-algorithms","category-c-programming-3","category-coding","tag-c-program-to-find-numbers-divisible-by-5","tag-c-program-to-print-numbers-divisible-by-3-and-5","tag-c-program-to-print-numbers-divisible-by-7","tag-c-check-if-number-is-divisible-by-2","tag-c-divisible-by-5","tag-c-number-divisible-by-3","tag-c-program-to-find-numbers-divisible-by-7","tag-divisibility-program-in-c","tag-divisible-by-2-or-3-c-program","tag-divisible-numbers-count-program","tag-number-divisible-by-7-only","tag-write-a-c-program-to-check-whether-the-given-number-is-divisible-by-7-or-not","tag-write-a-program-that-prints-yes-if-the-given-integer-is-divisible-by-2-or-3-and-no-otherwise"],"_links":{"self":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26664","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/comments?post=26664"}],"version-history":[{"count":0,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/posts\/26664\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/media?parent=26664"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/categories?post=26664"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.wikitechy.com\/technology\/wp-json\/wp\/v2\/tags?post=26664"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}